QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#446141#21566. 四维偏序propane100 ✓385ms9948kbC++142.7kb2024-06-16 22:34:272024-06-16 22:34:27

Judging History

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

  • [2024-06-16 22:34:27]
  • 评测
  • 测评结果:100
  • 用时:385ms
  • 内存:9948kb
  • [2024-06-16 22:34:27]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
enum type {LEFT, RIGHT};

const int maxn = 1e5 + 5;

namespace BIT{

int tr[maxn];

int lowbit(int x){
    return x & -x;
}

void modify(int x, int v){
    while(x < maxn){
        tr[x] += v;
        x += lowbit(x);
    }
}

int query(int x){
    int ans = 0;
    while(x > 0){
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

}

struct Node{
    int a, b, c, d, type;

    bool operator<(const Node &t) const {
        return a < t.a;
    }

}p[maxn], q[maxn], w[maxn];

LL solve(int l, int r){
    if (l >= r) return 0LL;
    int mid = (l + r) / 2;
    int pl = l, pr = mid + 1, pt = l;
    LL ans = solve(l, mid) + solve(mid + 1, r);
    while(pl <= mid and pr <= r){
        if (q[pl].c < q[pr].c){
            if (q[pl].type == LEFT){
                BIT::modify(q[pl].d, 1);
            }
            w[pt++] = q[pl++];
        }
        else{
            if (q[pr].type == RIGHT){
                ans += BIT::query(q[pr].d - 1);
            }
            w[pt++] = q[pr++];
        }
    }
    while(pl <= mid){
        if (q[pl].type == LEFT){
            BIT::modify(q[pl].d, 1);
        }
        w[pt++] = q[pl++];
    }
    while(pr <= r){
        if (q[pr].type == RIGHT){
            ans += BIT::query(q[pr].d - 1);
        }
        w[pt++] = q[pr++];
    }
    for(int i = l; i <= mid; i++){
        if (q[i].type == LEFT){
            BIT::modify(q[i].d, -1);
        }
    }
    for(int i = l; i <= r; i++) q[i] = w[i];
    return ans;
}

LL cdq(int l, int r){
    if (l >= r) return 0LL;
    int mid = (l + r) / 2;
    LL ans = cdq(l, mid) + cdq(mid + 1, r);
    int pl = l, pr = mid + 1, pt = l;
    while(pl <= mid and pr <= r){
        if (p[pl].b < p[pr].b){
            q[pt++] = p[pl++];
            q[pt - 1].type = LEFT;
        }
        else{
            q[pt++] = p[pr++];
            q[pt - 1].type = RIGHT;
        }
    }
    while(pl <= mid){
        q[pt++] = p[pl++];
        q[pt - 1].type = LEFT;
    }
    while(pr <= r){
        q[pt++] = p[pr++];
        q[pt - 1].type = RIGHT;
    }
    for(int i = l; i <= r; i++){
        p[i] = q[i];
    }
    ans += solve(l, r);
    return ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d;
    }
    sort(p + 1, p + n + 1);
    cout << cdq(1, n) << '\n';

}

详细

Test #1:

score: 10
Accepted
time: 176ms
memory: 8996kb

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: 164ms
memory: 8752kb

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: 177ms
memory: 8900kb

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: 169ms
memory: 9896kb

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: 176ms
memory: 9744kb

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: 383ms
memory: 9892kb

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: 382ms
memory: 9800kb

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: 377ms
memory: 9948kb

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: 384ms
memory: 9900kb

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: 385ms
memory: 9892kb

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