QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#327587 | #3160. Cutting | bachbeo2007 | 20 | 168ms | 35144kb | C++20 | 6.3kb | 2024-02-15 11:01:32 | 2024-02-15 11:01:33 |
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;
if(tree[id<<1]>=1){
tree[id<<1]=lazy[id<<1]=lazy[id];
}
if(tree[id<<1|1]>=1){
tree[id<<1|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]);
if(tree[id]>=1) 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;
}
void update_pos(int l,int r,int id,int p,int val){
if(l==r){
tree[id]=val;
return;
}
pushdown(id);
int mid=(l+r)>>1;
if(p<=mid) update_pos(l,mid,id<<1,p,val);
else update_pos(mid+1,r,id<<1|1,p,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,H,0};
l[++n]={0,0,0,W};
l[++n]={H,0,H,W};
l[++n]={0,W,H,W};
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);
}
}
//cout << ans << '\n';
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){
cc[l[t].y]^=1;
//cout << "change " << id << '\n';
if(id>0) Segtree::update_pos(1,sy,1,l[t].y,t);
else Segtree::update_pos(1,sy,1,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){
//cout << '*' << t << '\n';
Segtree::update(1,sy,1,l[t].y,l[t].v,t);
ans+=BIT::query(l[t].v-1)-BIT::query(l[t].y)+1;
//cout << t << ' ' << BIT::query(l[t].v-1)-BIT::query(l[t].y) << '\n';
if(!cc[l[t].v]){
ans--;
//cout << "stupid\n";
}
if(!cc[l[t].y]){
ans--;
//cout << "stupid\n";
}
}
}
}
//cout << ans << '\n';
//cout << DSU::cnt << '\n';
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();
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 11772kb
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:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11880kb
input:
10 10 10 5 7 8 7 3 3 4 3 0 5 10 5 9 0 9 8 5 2 9 2 2 1 2 7 0 8 8 8 7 0 7 1 2 7 4 7 9 9 10 9
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 2ms
memory: 11824kb
input:
10 10 15 1 1 4 1 5 8 9 8 4 2 4 3 5 1 5 7 5 1 10 1 9 8 9 10 3 3 3 8 1 0 1 9 9 0 9 5 9 9 10 9 1 9 7 9 2 5 3 5 4 4 4 6 5 4 8 4 1 7 9 7
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 0ms
memory: 11836kb
input:
100 100 100 31 29 31 83 36 54 36 77 11 16 51 16 20 24 20 82 7 1 7 43 46 14 64 14 77 35 77 94 8 26 82 26 59 43 85 43 55 18 94 18 97 22 97 90 46 61 75 61 78 6 78 20 74 3 74 85 34 93 97 93 87 45 98 45 57 23 82 23 5 58 64 58 55 92 58 92 9 10 9 49 8 5 57 5 17 88 61 88 48 68 48 73 53 51 93 51 7 29 85 29 5...
output:
303
result:
ok single line: '303'
Test #5:
score: -5
Wrong Answer
time: 1ms
memory: 11852kb
input:
100 100 144 47 22 89 22 12 12 12 99 94 21 94 64 83 93 83 98 27 29 78 29 18 43 76 43 19 57 29 57 22 33 22 90 71 61 82 61 27 1 27 100 9 47 56 47 37 34 44 34 32 23 89 23 35 58 89 58 8 78 13 78 97 90 97 91 19 7 39 7 29 27 55 27 80 79 88 79 33 8 76 8 6 48 54 48 46 73 46 97 48 53 61 53 92 52 92 53 10 19 2...
output:
782
result:
wrong answer 1st lines differ - expected: '781', found: '782'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 20
Accepted
Test #29:
score: 20
Accepted
time: 2ms
memory: 11988kb
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:
10525
result:
ok single line: '10525'
Test #30:
score: 0
Accepted
time: 3ms
memory: 13944kb
input:
1000 1000000000 603 601 755190731 601 810458592 934 408413681 934 991509232 677 999530155 815 999530155 168 493643722 673 493643722 471 611014716 471 737416010 297 338288031 560 338288031 359 95457712 359 618830356 526 343959777 881 343959777 925 444786130 925 668860824 514 666804490 514 983701500 6...
output:
9023
result:
ok single line: '9023'
Test #31:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
1000000000 1000 497 827959903 211 827959903 713 423671814 326 423671814 505 151915634 787 151915634 939 973586233 330 973586233 372 243989833 294 381424364 294 852825911 110 852825911 211 656054851 649 980370982 649 361463145 400 562481084 400 598057245 206 598057245 519 356401865 441 356401865 641 ...
output:
6182
result:
ok single line: '6182'
Test #32:
score: 0
Accepted
time: 2ms
memory: 11940kb
input:
1000000000 1000000000 1000 630608407 74813188 630608407 572572115 428810287 713956480 539731989 713956480 640066404 189916304 777953387 189916304 139692089 138020424 436628489 138020424 232274854 245431711 232274854 706217149 76021996 254360470 90280084 254360470 78051453 144768536 78051453 46597063...
output:
7634
result:
ok single line: '7634'
Test #33:
score: 0
Accepted
time: 12ms
memory: 17408kb
input:
1000000000 1000000000 10000 669049628 139158927 669049628 226133259 718482206 453214864 721640027 453214864 922685361 202362178 922685361 269486043 176418025 189329098 176418025 207938401 924551310 799389698 971274232 799389698 913658655 45406740 913658655 115315119 684126650 488289248 684126650 538...
output:
49135
result:
ok single line: '49135'
Test #34:
score: 0
Accepted
time: 79ms
memory: 23000kb
input:
1000000000 1000000000 50000 238613172 391515513 238613172 405815949 228020608 514039210 228020608 525135195 764909506 76206052 767077509 76206052 120043781 289917261 130315212 289917261 838856354 367766371 838856354 377711111 190255664 959215979 190255664 960991962 152573495 152153917 162261418 1521...
output:
23820
result:
ok single line: '23820'
Test #35:
score: 0
Accepted
time: 156ms
memory: 34888kb
input:
1000000000 1000000000 100000 170340118 373306152 170340118 379627430 12604058 168765839 12604058 170795182 20332951 541320438 20332951 549298071 134940794 461595827 134940794 470870367 311164461 197351124 311164461 202291947 421842363 147731250 422869432 147731250 282491926 152715320 282491926 15528...
output:
9721
result:
ok single line: '9721'
Test #36:
score: 0
Accepted
time: 168ms
memory: 35144kb
input:
1000000000 1000000000 100000 648681835 61387068 648681835 61467529 482483617 633133302 490538368 633133302 238416060 954280004 238416060 960579571 971671652 48097001 971671652 52691091 961774046 226207867 961774046 234611274 143188037 361192114 152157365 361192114 631586268 619581854 639748156 61958...
output:
23400
result:
ok single line: '23400'
Test #37:
score: 0
Accepted
time: 153ms
memory: 32436kb
input:
1000000000 1000000000 100000 533066721 267929372 533066721 268068695 478609871 93625392 478609871 94238869 509029333 579208129 509709352 579208129 712522492 727418412 712719154 727418412 272180063 572902914 272180063 573774712 758504262 227729418 759289998 227729418 637434739 129362617 637434739 130...
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 127ms
memory: 25440kb
input:
1000000000 1000000000 100000 273576603 753501145 273576631 753501145 209049647 751024536 209049647 751024584 730324450 156458455 730324489 156458455 462842489 975962094 462842489 975962116 539789616 391587975 539789616 391588008 443086141 242291883 443086228 242291883 935928542 938420909 935928542 9...
output:
1
result:
ok single line: '1'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%