QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #740088 | #21566. 四维偏序 | I_be_wanna | 100 ✓ | 353ms | 9952kb | C++20 | 4.8kb | 2024-11-13 00:58:16 | 2024-11-13 00:58:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;long long ans;
struct node{int a,b,c,d,tp;}q[N],tmp1[N],tmp2[N];
inline bool cmp1(node x,node y){return x.a<y.a;}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
struct tree{
int cc[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v)
{
for(;x<=n;x+=lowbit(x))cc[x]+=v;
}
inline int query(int x)
{
int anss=0;
for(;x;x-=lowbit(x))anss+=cc[x];
return anss;
}
}T;
void cdq3d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq3d(l,mid);cdq3d(mid+1,r);
int i=l,j=mid+1,cnt2=l;
while(j<=r)
{
while(tmp1[i].c<tmp1[j].c&&i<=mid)
{
if(tmp1[i].tp==1) T.add(tmp1[i].d,1);
tmp2[cnt2++]=tmp1[i++];
}
if(tmp1[j].tp==2) ans+=T.query(tmp1[j].d);
tmp2[cnt2++]=tmp1[j++];
}
for(int e=l;e<i;++e)
if(tmp1[e].tp==1) T.add(tmp1[e].d,-1);
for(int e=i;e<=mid;++e) tmp2[cnt2++]=tmp1[e];
for(int e=l;e<=r;++e) tmp1[e]=tmp2[e];
}
void cdq2d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq2d(l,mid);cdq2d(mid+1,r);
int i=l,j=mid+1,cnt1=l;
while(j<=r)
{
while(q[i].b<q[j].b&&i<=mid) q[i].tp=1,tmp1[cnt1++]=q[i++];
q[j].tp=2,tmp1[cnt1++]=q[j++];
}
for(int e=i;e<=mid;++e) q[e].tp=1,tmp1[cnt1++]=q[e];
for(int e=l;e<=r;++e) q[e]=tmp1[e];
cdq3d(l,r);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)q[i].a=read(),q[i].b=read(),q[i].c=read(),q[i].d=read();
sort(q+1,q+n+1,cmp1);
cdq2d(1,n);
cout<<ans;
return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;long long ans;
struct node{int a,b,c,d,tp;}q[N],tmp1[N],tmp2[N];
inline bool cmp1(node x,node y){return x.a<y.a;}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
struct tree{
int cc[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v)
{
for(;x<=n;x+=lowbit(x))cc[x]+=v;
}
inline int query(int x)
{
int anss=0;
for(;x;x-=lowbit(x))anss+=cc[x];
return anss;
}
}T;
void cdq3d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq3d(l,mid);cdq3d(mid+1,r);
int i=l,j=mid+1,cnt2=l;
while(j<=r)
{
while(tmp1[i].c<tmp1[j].c&&i<=mid)
{
if(tmp1[i].tp==1) T.add(tmp1[i].d,1);
tmp2[cnt2++]=tmp1[i++];
}
if(tmp1[j].tp==2) ans+=T.query(tmp1[j].d);
tmp2[cnt2++]=tmp1[j++];
}
for(int e=l;e<i;++e)
if(tmp1[e].tp==1) T.add(tmp1[e].d,-1);
for(int e=i;e<=mid;++e) tmp2[cnt2++]=tmp1[e];
for(int e=l;e<=r;++e) tmp1[e]=tmp2[e];
}
void cdq2d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq2d(l,mid);cdq2d(mid+1,r);
int i=l,j=mid+1,cnt1=l;
while(j<=r)
{
while(q[i].b<q[j].b&&i<=mid) q[i].tp=1,tmp1[cnt1++]=q[i++];
q[j].tp=2,tmp1[cnt1++]=q[j++];
}
for(int e=i;e<=mid;++e) q[e].tp=1,tmp1[cnt1++]=q[e];
for(int e=l;e<=r;++e) q[e]=tmp1[e];
cdq3d(l,r);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)q[i].a=read(),q[i].b=read(),q[i].c=read(),q[i].d=read();
sort(q+1,q+n+1,cmp1);
cdq2d(1,n);
cout<<ans;
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;long long ans;
struct node{int a,b,c,d,tp;}q[N],tmp1[N],tmp2[N];
inline bool cmp1(node x,node y){return x.a<y.a;}
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
struct tree{
int cc[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int v)
{
for(;x<=n;x+=lowbit(x))cc[x]+=v;
}
inline int query(int x)
{
int anss=0;
for(;x;x-=lowbit(x))anss+=cc[x];
return anss;
}
}T;
void cdq3d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq3d(l,mid);cdq3d(mid+1,r);
int i=l,j=mid+1,cnt2=l;
while(j<=r)
{
while(tmp1[i].c<tmp1[j].c&&i<=mid)
{
if(tmp1[i].tp==1) T.add(tmp1[i].d,1);
tmp2[cnt2++]=tmp1[i++];
}
if(tmp1[j].tp==2) ans+=T.query(tmp1[j].d);
tmp2[cnt2++]=tmp1[j++];
}
for(int e=l;e<i;++e)
if(tmp1[e].tp==1) T.add(tmp1[e].d,-1);
for(int e=i;e<=mid;++e) tmp2[cnt2++]=tmp1[e];
for(int e=l;e<=r;++e) tmp1[e]=tmp2[e];
}
void cdq2d(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq2d(l,mid);cdq2d(mid+1,r);
int i=l,j=mid+1,cnt1=l;
while(j<=r)
{
while(q[i].b<q[j].b&&i<=mid) q[i].tp=1,tmp1[cnt1++]=q[i++];
q[j].tp=2,tmp1[cnt1++]=q[j++];
}
for(int e=i;e<=mid;++e) q[e].tp=1,tmp1[cnt1++]=q[e];
for(int e=l;e<=r;++e) q[e]=tmp1[e];
cdq3d(l,r);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)q[i].a=read(),q[i].b=read(),q[i].c=read(),q[i].d=read();
sort(q+1,q+n+1,cmp1);
cdq2d(1,n);
cout<<ans;
return 0;
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 152ms
memory: 8720kb
input:
49995 25201 24841 32082 47399 11858 35036 36484 24573 28368 8935 35040 10246 23421 18221 28778 25594 13980 42394 47584 47243 9732 29095 25460 10151 36904 19647 24412 16243 10069 16471 20628 8669 47214 43247 23698 49530 42218 37968 26068 35481 48927 45376 10770 26532 48097 11865 4913 25311 6412 16257...
output:
188938349
result:
ok single line: '188938349'
Test #2:
score: 10
Accepted
time: 156ms
memory: 8692kb
input:
49997 39191 24440 33693 28479 41996 32707 47350 3311 30285 44451 7461 38543 40380 45414 4751 19900 31957 37065 24909 40388 48485 10004 31386 24932 8200 23527 39784 20642 48507 35443 48730 10164 42593 643 44221 14678 25759 32952 36341 32665 21052 2385 15155 44041 33862 31281 31847 28304 38034 32573 3...
output:
187908530
result:
ok single line: '187908530'
Test #3:
score: 10
Accepted
time: 156ms
memory: 8804kb
input:
49993 15704 40275 28199 37576 11636 23979 39224 42558 30195 49051 14472 41954 30757 1106 48320 28027 12818 44627 5050 35972 16825 29649 1978 37838 48347 36342 34654 37324 47144 26121 25980 39370 15029 22038 43108 44296 45405 36989 27455 36048 35069 32406 29158 23754 8626 32340 30765 24803 14709 4719...
output:
187391225
result:
ok single line: '187391225'
Test #4:
score: 10
Accepted
time: 156ms
memory: 8920kb
input:
49995 47120 12943 38136 14837 38570 28835 36055 30539 47574 26942 12879 23038 33124 8358 8818 17659 39442 49141 42952 7178 43709 49774 39916 25962 45195 11192 34831 10205 38617 41991 15702 48060 40193 36820 5097 32505 48504 38804 49449 16509 30019 19370 48801 36256 26166 34505 6035 45587 45140 32176...
output:
188643952
result:
ok single line: '188643952'
Test #5:
score: 10
Accepted
time: 152ms
memory: 8844kb
input:
49997 12981 34193 43546 30038 12385 26386 14914 10769 38576 28536 29531 41028 38886 26895 41350 24943 37840 36113 23276 28552 32521 12500 26345 26098 8583 27277 27193 21987 47140 34380 29909 16596 32275 2429 45729 38029 43119 41980 29028 18002 31598 48409 28149 45671 29131 37221 40298 47662 42088 29...
output:
189511997
result:
ok single line: '189511997'
Test #6:
score: 10
Accepted
time: 349ms
memory: 9884kb
input:
99995 74835 97387 39179 33679 85030 36478 82691 53293 28368 60234 94435 88525 68215 28772 95398 69882 92388 97231 87049 90370 79089 60139 48473 32699 36904 18772 73511 70624 66465 28536 85427 51624 93241 99518 42581 64660 87962 85469 82936 82647 95370 76520 14432 94023 61859 75299 33850 70932 66251 ...
output:
1777930616
result:
ok single line: '1777930616'
Test #7:
score: 10
Accepted
time: 352ms
memory: 9880kb
input:
99992 90251 87545 62907 38103 71466 92527 78799 36022 99027 91923 73231 72803 1855 77996 33094 67620 94603 85941 99105 57139 79625 87807 99738 75923 86318 87293 61156 34798 76097 89339 91955 98021 72014 94265 86784 82466 86965 86017 88768 66470 82382 73723 68235 86217 82316 74772 84469 95548 97167 8...
output:
1776662757
result:
ok single line: '1776662757'
Test #8:
score: 10
Accepted
time: 350ms
memory: 9816kb
input:
99994 84153 71558 79019 82707 76346 14877 99937 57295 78496 90987 46483 81919 52697 74902 78707 12498 86073 27723 99406 87853 32485 76057 46713 39996 53270 71946 73538 26099 84340 66555 57692 29368 25984 87988 77952 21691 91940 67377 91211 76523 98369 95630 93021 86644 87181 97621 54310 54683 79891 ...
output:
1775939702
result:
ok single line: '1775939702'
Test #9:
score: 10
Accepted
time: 353ms
memory: 9952kb
input:
99997 91687 96540 97158 4337 87660 16364 23596 98356 90574 38284 36545 70969 39122 63052 58092 49390 97611 94875 91161 20876 97397 89674 91128 53918 71814 71773 91969 95858 30271 80365 57931 90529 94571 97532 72050 83937 23363 87395 99412 81922 28530 69593 84988 95532 54466 54614 62210 71213 84779 8...
output:
1784772992
result:
ok single line: '1784772992'
Test #10:
score: 10
Accepted
time: 351ms
memory: 9816kb
input:
99991 68618 96111 78352 52543 77189 66020 29990 98377 84523 99409 39471 97281 73251 90624 14746 70252 65227 86828 9641 69720 87552 7915 98953 55794 78937 23325 77330 92393 1284 76664 65953 95158 92860 95396 42615 7191 28564 93668 96153 50707 62620 30083 88670 39757 32744 44380 84802 98233 83306 1204...
output:
1787328379
result:
ok single line: '1787328379'
Extra Test:
score: 0
Extra Test Passed