QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#9726 | #21566. 四维偏序 | RainAir# | 100 ✓ | 501ms | 8508kb | C++11 | 2.6kb | 2021-04-09 18:22:29 | 2021-12-19 11:43:26 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1e5 + 5;
int A[MAXN],B[MAXN],C[MAXN],D[MAXN],a[MAXN],tmpa[MAXN],n;
LL ans = 0;
P<int,int> b[MAXN],tmpb[MAXN];
struct BIT{
#define lowbit(x) ((x)&(-(x)))
int tree[MAXN],ts[MAXN],now;
BIT(){now = 0;}
inline void clear(){++now;}
inline void add(int p,int x){
for(;p < MAXN;p += lowbit(p)){
if(ts[p] != now) tree[p] = 0,ts[p] = now;
tree[p] += x;
}
}
inline int query(int p){
int res = 0;
for(;p;p -= lowbit(p)){
if(ts[p] != now) tree[p] = 0,ts[p] = now;
res += tree[p];
}
return res;
}
}bit;
inline void cdq2(int l,int r){
if(l == r) return;
int mid = (l + r) >> 1;
cdq2(l,mid);cdq2(mid+1,r);
int p1 = l,p2 = mid+1,t = l-1;bit.clear();
while(p1 <= mid && p2 <= r){
if(C[b[p1].fi] < C[b[p2].fi]){
if(!b[p1].se) bit.add(D[b[p1].fi],1);
tmpb[++t] = b[p1++];
}
else{
if(b[p2].se) ans += bit.query(D[b[p2].fi]-1);
tmpb[++t] = b[p2++];
}
}
// FOR(i,l,r) printf("%d %d\n",b[i].fi,b[i].se);
FOR(i,p1,mid) tmpb[++t] = b[i];
FOR(i,p2,r){
tmpb[++t] = b[i];
if(b[i].se) ans += bit.query(D[b[i].fi]-1);
}
FOR(i,l,r) b[i] = tmpb[i];
}
inline void cdq1(int l,int r){
if(l == r) return;
int mid = (l + r) >> 1;
cdq1(l,mid);cdq1(mid+1,r);
// 0 = add 1 = qry
int p1 = l,p2 = mid+1,tot = 0,t = l-1;
while(p1 <= mid && p2 <= r){
if(B[a[p1]] < B[a[p2]]) b[++tot] = MP(a[p1],0),tmpa[++t] = a[p1++];
else b[++tot] = MP(a[p2],1),tmpa[++t] = a[p2++];
}
FOR(i,p1,mid) tmpa[++t] = a[i];
FOR(i,p2,r) b[++tot] = MP(a[i],1),tmpa[++t] = a[i];
// DEBUG(l);DEBUG(r);
cdq2(1,tot);
FOR(i,l,r) a[i] = tmpa[i];
}
int main(){
//freopen("A.in","r",stdin);
//freopen("A.out","w",stdout);
scanf("%d",&n);
FOR(i,1,n) scanf("%d%d%d%d",A+i,B+i,C+i,D+i),a[i] = i;
std::sort(a+1,a+n+1,[&](int x,int y){return A[x] < A[y];});
cdq1(1,n);
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 211ms
memory: 7080kb
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 47628 28786 30174 16671 34227 9097 31110 3631 24148 49536 49224 14872 39974 27460 5769 35721 25661 22494 15560 31839 16347 38779 18812 37221 35730 47813 29015 42849 16836 14857 13362 35038 44502 2735...
output:
188938349
result:
ok single line: '188938349'
Test #2:
score: 10
Accepted
time: 209ms
memory: 7064kb
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 37904 14492 25729 43071 644 23123 41058 22376 43258 29108 19707 48487 40647 34757 22544 21291 42748 43349 11323 45925 25812 27029 33587 14901 32311 31218 7905 16502 46505 38405 33752 37574 23168 27935 ...
output:
187908530
result:
ok single line: '187908530'
Test #3:
score: 10
Accepted
time: 215ms
memory: 7060kb
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 47191 42693 34123 14534 38502 21628 22813 25418 45496 30987 33830 16979 44342 48256 45713 21279 31092 30523 31248 8073 43876 48691 43878 41800 32645 37472 1233 43516 31157 13594 14171 47238 15476 45978 48...
output:
187391225
result:
ok single line: '187391225'
Test #4:
score: 10
Accepted
time: 205ms
memory: 7104kb
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 24690 31937 21484 42072 2706 29075 24667 46894 43135 42993 41620 27567 22531 45143 46467 44271 47540 37027 17397 32154 3212 9903 38249 46107 41877 347 46606 16316 19037 13782 33104 46479 42194 48355 ...
output:
188643952
result:
ok single line: '188643952'
Test #5:
score: 10
Accepted
time: 223ms
memory: 7124kb
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 29931 22592 31264 47879 11497 24160 41595 42660 28915 43035 49602 17560 48933 17544 35150 24480 28233 40541 11821 15454 49041 7753 33484 40289 48123 27287 31266 14432 29442 45961 38355 26627 21252 13727...
output:
189511997
result:
ok single line: '189511997'
Test #6:
score: 10
Accepted
time: 501ms
memory: 8344kb
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 78774 38022 53407 30174 58879 93055 69506 31110 99524 63150 72013 53487 61406 98471 84739 85715 72482 71275 93331 81833 88767 95909 62884 87215 97801 64885 20731 92843 52292 66486 88387 85032 77338 87...
output:
1777930616
result:
ok single line: '1777930616'
Test #7:
score: 10
Accepted
time: 446ms
memory: 8408kb
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 84092 56901 81898 88478 72782 92036 70121 95472 83799 96858 92954 94318 95682 77531 95104 7001 30500 94235 86988 93852 93847 82118 12715 82621 37449 96071 41844 81133 64140 46576 10295 47222 98045 9644...
output:
1776662757
result:
ok single line: '1776662757'
Test #8:
score: 10
Accepted
time: 493ms
memory: 8508kb
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 81223 94094 80233 47843 91554 9218 95688 78875 99561 96935 17802 98893 85109 86626 67061 78193 61780 96437 36890 99001 83443 48035 95407 98083 64143 71144 66548 56560 88314 82625 66707 56153 83120 519...
output:
1775939702
result:
ok single line: '1775939702'
Test #9:
score: 10
Accepted
time: 460ms
memory: 8320kb
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 88904 58248 86360 83761 94310 95514 24136 4677 56627 73251 78114 62167 36924 81482 98005 42620 91480 93327 98949 28637 97279 97133 54896 89689 93757 82695 79578 65040 20858 64056 72507 64169 69529 6603...
output:
1784772992
result:
ok single line: '1784772992'
Test #10:
score: 10
Accepted
time: 446ms
memory: 8332kb
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 12040 95834 87503 28025 46845 96251 92416 90616 43672 61016 43856 87080 95885 79886 82733 79850 95749 33115 15487 53785 99773 75510 99907 61811 53136 94913 82957 59209 92474 96570 13838 83949 75106 59289 ...
output:
1787328379
result:
ok single line: '1787328379'
Extra Test:
score: 0
Extra Test Passed