QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#327566 | #3160. Cutting | bachbeo2007 | 0 | 2ms | 9896kb | C++20 | 5.3kb | 2024-02-15 10:30:24 | 2024-02-15 10:30:24 |
Judging History
answer
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=100015;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
const int iroot=power(3,mod-2);
const int base=101;
int sx,sy;
vector<int> cx,cy;
vector<int> qq[2*maxn];
int cc[2*maxn];
namespace DSU{
int cnt,par[maxn];
void init(int n){
cnt=n;
for(int i=1;i<=n;i++) par[i]=i;
}
int findpar(int u){
if(u!=par[u]) return par[u]=findpar(par[u]);
return u;
}
void unions(int u,int v){
if(!u || !v) return;
u=findpar(u);v=findpar(v);
if(u==v) return;
par[v]=u;cnt--;
}
};
namespace BIT{
int bit[2*maxn],sz;
void init(int n){
sz=n;
for(int i=1;i<=n;i++) bit[i]=0;
}
void update(int x,int val){
for(int i=x;i<=sz;i+=(i&(-i))) bit[i]+=val;
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
return res;
}
}
namespace Segtree{
int tree[8*maxn],lazy[8*maxn];
void pushdown(int id){
if(!lazy[id]) return;
tree[id<<1]=tree[id<<1|1]=lazy[id<<1]=lazy[id<<1|1]=lazy[id];
lazy[id]=0;
}
void update(int l,int r,int id,int tl,int tr,int val){
if(tr<l || r<tl) return;
if(tl<=l && r<=tr && tree[id]!=-1){
DSU::unions(val,tree[id]);
tree[id]=lazy[id]=val;
return;
}
pushdown(id);
int mid=(l+r)>>1;
update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
int a=tree[id<<1],b=tree[id<<1|1];
if(a>b) swap(a,b);
if(a>0){
if(a==b) tree[id]=a;
else tree[id]=-1;
}
else if(a==0) tree[id]=b;
else tree[id]=-1;
}
}
int H,W,N,n;
struct line{
int x,y,u,v;
}l[maxn];
void solve(){
cin >> H >> W >> N;
for(int i=1;i<=N;i++){
int x,y,u,v;cin >> x >> y >> u >> v;
if(x!=u || y!=v) l[++n]={x,y,u,v};
}
l[++n]={0,0,W,0};
l[++n]={0,0,0,H};
l[++n]={W,0,W,H};
l[++n]={0,H,W,H};
for(int i=1;i<=n;i++){
cx.push_back(l[i].x);
cx.push_back(l[i].u+1);
cy.push_back(l[i].y);
cy.push_back(l[i].v+1);
}
sort(cx.begin(),cx.end());
sort(cy.begin(),cy.end());
cx.erase(unique(cx.begin(),cx.end()),cx.end());
cy.erase(unique(cy.begin(),cy.end()),cy.end());
sx=(int)cx.size()-1;sy=(int)cy.size()-1;
int ans=0;
for(int i=1;i<=n;i++){
l[i].x=lower_bound(cx.begin(),cx.end(),l[i].x)-cx.begin()+1;
l[i].u=lower_bound(cx.begin(),cx.end(),l[i].u+1)-cx.begin();
l[i].y=lower_bound(cy.begin(),cy.end(),l[i].y)-cy.begin()+1;
l[i].v=lower_bound(cy.begin(),cy.end(),l[i].v+1)-cy.begin();
if(l[i].x==l[i].u) qq[l[i].x].push_back(i);
else{
ans--;
//cout << '*' << i << '\n';
qq[l[i].x].push_back(i);
qq[l[i].u+1].push_back(-i);
}
}
DSU::init(n);
BIT::init(sy);
for(int i=1;i<=sx;i++){
for(int id:qq[i]){
int t=abs(id);
if(l[t].x==l[t].u) Segtree::update(1,sy,1,l[t].y,l[t].v,t);
else{
cc[l[t].y]^=1;
if(id>0) Segtree::update(1,sy,1,l[t].y,l[t].y,t);
else Segtree::update(1,sy,1,l[t].y,l[t].y,0);
BIT::update(l[t].y,(id<0?-1:1));
}
}
for(int id:qq[i]){
int t=abs(id);
if(l[t].x==l[t].u){
ans+=BIT::query(l[t].v-1)-BIT::query(l[t].y)+1;
if(!cc[l[t].v]) ans--;
if(!cc[l[t].y]) ans--;
}
}
}
ans+=DSU::cnt;
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9856kb
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:
0
result:
wrong answer 1st lines differ - expected: '3', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #29:
score: 0
Wrong Answer
time: 2ms
memory: 9896kb
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:
10512
result:
wrong answer 1st lines differ - expected: '10525', found: '10512'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%