QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403086#4071. Galactic Collegiate Programming ContestQRQRQRAC ✓126ms11036kbC++17880b2024-05-01 20:33:442024-05-01 20:33:45

Judging History

This is the latest submission verdict.

  • [2024-05-01 20:33:45]
  • Judged
  • Verdict: AC
  • Time: 126ms
  • Memory: 11036kb
Show
  • [2024-05-01 20:33:44]
  • Submitted

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define ranktree tree<pair<pii, int>, null_type, greater<pair<pii, int>>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

ranktree rt;
int n, m;
pair<pii, int> team[100005];

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) team[i].F.F = team[i].F.S = team[i].S =  0;
    for (int i = 0; i < m; i++) {
        int tt, pp;
        cin >> tt >> pp;
        auto it = rt.find(team[tt]);
        if (it != rt.end()) rt.erase(it);
        team[tt].F.F++;
        team[tt].F.S -= pp;
        team[tt].S = -tt;
        rt.insert(team[tt]);
        int rk = rt.order_of_key(team[1]);
        cout << rk+1 << "\n";
    }
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

3 4
2 7
3 5
1 6
1 9

output:

2
3
2
1

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 43ms
memory: 4788kb

input:

100000 100000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 60ms
memory: 4796kb

input:

100000 100000
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 56ms
memory: 4736kb

input:

100000 100000
5 1
1 1
1 1
2 1
1 1
2 1
4 1
4 1
1 1
4 1
1 1
2 1
1 1
2 1
3 1
5 1
1 1
2 1
1 1
1 1
2 1
2 1
1 1
3 1
3 1
5 1
3 1
1 1
2 1
1 1
2 1
5 1
4 1
4 1
4 1
4 1
2 1
2 1
3 1
5 1
2 1
3 1
3 1
3 1
5 1
1 1
3 1
3 1
1 1
3 1
1 1
2 1
5 1
5 1
3 1
4 1
3 1
3 1
2 1
4 1
3 1
2 1
1 1
2 1
1 1
4 1
1 1
3 1
2 1
1 1
4 1
4 ...

output:

2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
1
1
2
2
2
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 104ms
memory: 8748kb

input:

100000 100000
55327 1
99139 1
71762 1
29617 1
45413 1
25203 1
17598 1
12185 1
61815 1
34125 1
11875 1
42983 1
23226 1
83353 1
4102 1
36477 1
27664 1
30200 1
65341 1
7227 1
87024 1
88551 1
57914 1
17679 1
23141 1
29742 1
39939 1
21405 1
22572 1
91574 1
26588 1
30493 1
39818 1
48602 1
66761 1
6680 1
9...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 63ms
memory: 7192kb

input:

100000 100000
30482 1
76250 1
37507 1
1 1
1 1
32309 1
49333 1
1 1
1 1
10246 1
1 1
1 1
72682 1
55670 1
1 1
1 1
1 1
1 1
1 1
1 1
46963 1
50193 1
55133 1
1 1
1 1
32898 1
1 1
49168 1
1 1
1 1
36014 1
1 1
1 1
93437 1
37362 1
3615 1
1 1
55953 1
76473 1
40943 1
1 1
37810 1
88470 1
33197 1
31007 1
30194 1
1 1...

output:

2
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 53ms
memory: 4796kb

input:

100000 100000
2 1
5 1
2 1
4 1
3 1
3 1
4 1
5 1
3 1
1 1
2 1
5 1
1 1
1 1
1 1
3 1
2 1
3 1
1 1
1 1
3 1
3 1
3 1
3 1
5 1
2 1
5 1
2 1
2 1
3 1
2 1
1 1
1 1
4 1
4 1
4 1
2 1
1 1
4 1
1 1
3 1
3 1
2 1
3 1
3 1
1 1
2 1
2 1
5 1
4 1
1 1
3 1
3 1
4 1
4 1
1 1
2 1
5 1
2 1
5 1
5 1
2 1
5 1
3 1
4 1
2 1
3 1
1 1
3 1
2 1
1 1
5 ...

output:

2
3
3
4
5
5
5
5
5
5
5
5
4
1
1
1
1
2
1
1
1
2
2
2
2
2
2
2
3
3
3
3
2
2
2
2
3
2
2
1
2
2
2
2
2
2
2
3
3
3
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
2
2
2
2
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 56ms
memory: 4792kb

input:

100000 100000
1 666
1 150
1 487
1 597
1 829
1 60
1 770
1 531
1 659
1 522
1 52
1 988
1 406
1 553
1 609
1 683
1 824
1 758
1 128
1 915
1 577
1 430
1 35
1 794
1 36
1 865
1 524
1 336
1 580
1 280
1 727
1 238
1 800
1 932
1 562
1 84
1 327
1 997
1 783
1 200
1 376
1 537
1 826
1 929
1 213
1 759
1 799
1 640
1 2...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 47ms
memory: 4816kb

input:

100000 100000
2 524
2 826
2 52
2 268
2 191
2 212
2 425
2 351
2 565
2 136
2 510
2 259
2 499
2 578
2 308
2 84
2 363
2 449
2 257
2 140
2 50
2 175
2 640
2 878
2 703
2 207
2 583
2 653
2 657
2 75
2 190
2 781
2 421
2 505
2 110
2 71
2 677
2 824
2 219
2 287
2 365
2 647
2 110
2 173
2 683
2 590
2 884
2 883
2 9...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 100000 lines

Test #10:

score: 0
Accepted
time: 55ms
memory: 4744kb

input:

100000 100000
4 575
4 298
1 21
2 149
3 865
5 379
5 503
5 330
1 642
3 704
1 228
5 582
3 63
3 605
1 101
3 810
3 160
4 390
2 802
2 650
5 649
3 335
2 953
4 381
2 651
5 331
5 881
5 183
1 554
2 211
1 504
4 959
3 590
2 517
3 873
2 41
3 8
3 162
1 331
1 411
1 688
5 301
1 827
5 169
5 723
4 455
3 633
1 27
4 92...

output:

2
2
2
2
2
2
3
3
2
2
1
2
2
3
1
2
2
2
2
2
3
3
3
3
4
4
4
4
3
4
3
3
3
4
4
4
4
4
4
2
2
2
2
2
3
3
3
2
2
3
3
3
2
2
2
2
3
3
3
3
3
4
4
4
4
4
4
4
4
2
3
3
3
4
4
4
2
2
2
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
2
3
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

result:

ok 100000 lines

Test #11:

score: 0
Accepted
time: 105ms
memory: 8808kb

input:

100000 100000
13278 186
88538 976
46258 767
2370 544
62288 858
28296 292
1752 493
7261 783
41911 520
80625 965
95940 593
65666 690
26657 428
39906 604
79096 623
31158 272
86458 957
44963 561
96358 510
28646 213
35836 796
69889 442
76394 192
62381 118
32711 870
12138 288
49465 231
79986 625
52150 501...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #12:

score: 0
Accepted
time: 88ms
memory: 7248kb

input:

100000 100000
2041 678
56284 687
34509 604
16106 421
94039 894
97202 737
1 196
1 568
1 144
1 455
1 824
15933 639
73732 657
1 451
1 402
1 135
17685 914
18978 1
33265 705
1 647
1 259
74744 671
15424 559
1 300
1 510
25208 290
97158 728
39486 547
1 590
1203 559
1 394
1 92
1 150
1 866
1 487
68679 337
1 6...

output:

2
3
4
5
6
7
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #13:

score: 0
Accepted
time: 52ms
memory: 4792kb

input:

100000 100000
1 95
3 813
3 958
5 300
3 14
1 215
3 421
3 961
1 548
3 656
5 29
3 888
4 536
3 567
5 325
2 179
3 144
5 6
2 118
4 411
4 222
1 689
3 836
3 280
1 948
4 272
2 274
1 75
3 605
4 49
5 20
5 858
1 392
5 210
5 582
2 469
1 363
4 883
4 659
1 365
5 549
2 50
1 11
4 721
2 677
4 355
4 800
3 996
4 336
3 ...

output:

1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
2
2
2
2
2
2
2
3
2
3
3
3
3
3
3
2
3
3
2
2
2
2
2
2
3
3
2
2
2
2
2
3
3
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
3
3
3
3
3
4
5
5
4
...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 126ms
memory: 11036kb

input:

100000 100000
2 1000
3 1000
4 1000
5 1000
6 1000
7 1000
8 1000
9 1000
10 1000
11 1000
12 1000
13 1000
14 1000
15 1000
16 1000
17 1000
18 1000
19 1000
20 1000
21 1000
22 1000
23 1000
24 1000
25 1000
26 1000
27 1000
28 1000
29 1000
30 1000
31 1000
32 1000
33 1000
34 1000
35 1000
36 1000
37 1000
38 100...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 71ms
memory: 7292kb

input:

100000 100000
2 200
3 200
97957 5
4 200
63738 1
5 200
90629 1
54951 3
6 200
7 200
78402 9
8 200
27499 10
29986 8
9 200
10 200
11 200
12 200
71892 2
13 200
81128 4
14 200
93267 6
15 200
87278 6
16 200
17 200
72775 2
18 200
15817 8
19 200
82892 2
20 200
87150 6
64633 10
21 200
22 200
11804 8
23 200
69...

output:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
10...

result:

ok 100000 lines
English 繁體中文 简体中文

Server Time: 2025-02-08 16:24:09 | OpenSource Project