QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345150 | #3160. Cutting | tuanlinh123 | 0 | 1ms | 3716kb | C++20 | 4.6kb | 2024-03-06 11:13:23 | 2024-03-06 11:13:23 |
Judging History
answer
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=100005;
ll a[maxn], b[maxn], c[maxn], d[maxn];
namespace BIT
{
ll n;
vector <ll> bit;
void init(ll sz) {n=sz, bit.assign(n+1, 0);}
void update(ll l, ll r)
{
for (; l<=n; l+=l&(-l)) bit[l]++;
for (++r; r<=n; r+=r&(-r)) bit[r]--;
}
ll query(ll i)
{
ll ans=0;
for (; i; i-=i&(-i)) ans+=bit[i];
return ans;
}
};
namespace DSU
{
ll n;
vector <ll> pa, Rank;
void init(ll sz)
{
n=sz, Rank.assign(n+1, 0);
pa.resize(n+1), iota(pa.begin(), pa.end(), 0);
}
ll Find(ll i)
{
if (pa[i]!=i) pa[i]=Find(pa[i]);
return pa[i];
}
void Union(ll a, ll b)
{
a=Find(a), b=Find(b);
if (a==b) return;
if (Rank[a]<Rank[b]) swap(a, b);
if (Rank[a]==Rank[b]) Rank[a]++;
pa[b]=a;
}
};
namespace SegTree
{
ll n;
vector <ll> St, lz;
void init(ll sz) {n=sz, St.assign(n*4+1, 0), lz.assign(n*4+1, 0);}
ll Merge(ll a, ll b)
{
if (a==-1 || b==-1 || (a>0 && b>0)) return -1;
return a+b;
}
void Move(ll i)
{
if (!lz[i]) return;
ll t=lz[i]; lz[i]=0;
St[i*2]=St[i*2+1]=lz[i*2]=lz[i*2+1]=t;
}
void update_ver(ll i, ll Start, ll End, ll idx, ll val)
{
if (Start>idx || End<idx) return;
if (Start==End) {St[i]=val; return;}
ll mid=(Start+End)/2;
if (idx<=mid) update_ver(i*2, Start, mid, idx, val);
else update_ver(i*2+1, mid+1, End, idx, val);
St[i]=Merge(St[i*2], St[i*2+1]);
}
void update_ver(ll idx, ll val) {update_ver(1, 1, n, idx, val);}
void update_hor(ll i, ll Start, ll End, ll l, ll r, ll val)
{
if (Start>r || End<l) return;
if (l<=Start && End<=r && St[i]!=-1)
{
if (St[i]) DSU::Union(val, St[i]), St[i]=lz[i]=val;
return;
}
ll mid=(Start+End)/2;
if (mid>=l) update_hor(i*2, Start, mid, l, r, val);
if (mid+1<=r) update_hor(i*2+1, mid+1, End, l, r, val);
St[i]=Merge(St[i*2], St[i*2+1]);
}
void update_hor(ll l, ll r, ll val) {update_hor(1, 1, n, l, r, val);}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll w, h, n; cin >> w >> h >> n; n+=4;
long long e=0, v=0;
vector <ll> cx, cy;
for (ll i=1; i<=n; i++)
{
if (i<=n-4) cin >> a[i] >> b[i] >> c[i] >> d[i];
if (i==n-3) a[i]=0, b[i]=0, c[i]=w, d[i]=0;
if (i==n-2) a[i]=0, b[i]=0, c[i]=0, d[i]=h;
if (i==n-1) a[i]=0, b[i]=h, c[i]=w, d[i]=h;
if (i==n) a[i]=w, b[i]=0, c[i]=w, d[i]=h;
cx.pb(a[i]), cx.pb(c[i]), cy.pb(b[i]), cy.pb(d[i]);
if (a[i]==c[i]) e+=d[i]-b[i], v+=d[i]-b[i]+1;
else e+=c[i]-a[i], v+=c[i]-a[i]+1;
}
sort(cx.begin(), cx.end());
cx.resize(unique(cx.begin(), cx.end())-cx.begin());
sort(cy.begin(), cy.end());
cy.resize(unique(cy.begin(), cy.end())-cy.begin());
ll kx=cx.size(), ky=cy.size();
DSU::init(n), SegTree::init(kx), BIT::init(kx);
vector <vector <pll>> event(ky+2);
for (ll i=1; i<=n; i++)
{
a[i]=lower_bound(cx.begin(), cx.end(), a[i])-cx.begin()+1;
b[i]=lower_bound(cy.begin(), cy.end(), b[i])-cy.begin()+1;
c[i]=lower_bound(cx.begin(), cx.end(), c[i])-cx.begin()+1;
d[i]=lower_bound(cy.begin(), cy.end(), d[i])-cy.begin()+1;
if (a[i]==c[i]) event[b[i]].pb({0, i}), event[d[i]+1].pb({0, -i});
else event[b[i]].pb({1, i});
}
for (ll i=1; i<=ky+1; i++)
{
sort(event[i].begin(), event[i].end());
for (pll j:event[i])
{
if (!j.fi)
{
if (j.se>0)
{
SegTree::update_ver(a[j.se], j.se);
v+=BIT::query(a[j.se]);
}
else
{
SegTree::update_ver(a[-j.se], 0);
v-=BIT::query(a[-j.se]);
}
}
else
{
SegTree::update_hor(a[j.se], c[j.se], j.se);
BIT::update(a[j.se], c[j.se]);
}
}
}
for (ll i=1; i<=n; i++)
if (DSU::pa[i]<0) e++;
cout << e-v << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3664kb
input:
10 10 10 6 5 6 10 4 0 4 3 3 2 3 10 0 8 2 8 3 8 5 8 0 2 7 2 9 6 9 8 8 2 8 7 5 3 6 3 1 1 7 1
output:
-1
result:
wrong answer 1st lines differ - expected: '3', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #29:
score: 0
Wrong Answer
time: 0ms
memory: 3716kb
input:
1000 1000 600 467 160 467 845 10 68 10 101 358 513 358 621 66 671 620 671 351 549 596 549 87 746 87 917 526 145 526 559 118 314 118 868 87 584 373 584 4 117 4 150 801 265 801 416 417 269 417 630 480 144 480 550 945 203 945 768 679 484 679 525 93 342 93 504 954 176 954 270 453 206 453 565 898 668 898...
output:
10511
result:
wrong answer 1st lines differ - expected: '10525', found: '10511'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%