QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#9726#21566. 四维偏序RainAir#100 ✓501ms8508kbC++112.6kb2021-04-09 18:22:292021-12-19 11:43:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 11:43:26]
  • 评测
  • 测评结果:100
  • 用时:501ms
  • 内存:8508kb
  • [2021-04-09 18:22:29]
  • 提交

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