QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#760359#9559. The TowerMiniLongAC ✓661ms620872kbC++205.2kb2024-11-18 16:29:002024-11-20 08:58:18

Judging History

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

  • [2024-11-20 08:58:18]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果：AC
  • 用时：661ms
  • 内存：620872kb
查看
  • [2024-11-20 08:41:35]
  • hack成功，自动添加数据
  • (/hack/1205)
  • [2024-11-18 16:29:01]
  • 评测
  • 测评结果：100
  • 用时：642ms
  • 内存：619972kb
查看
  • [2024-11-18 16:29:00]
  • 提交

answer

#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
    #ifdef ONLINE_JUDGE
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 5e5 + 5, _ = 1e9;
int n, cnt, id[N];
map<int, int> mp;
namespace sgt{
    int num, rt[N];
    int ls[N * 105], rs[N * 105], tr[N * 105], fa[N * 105];
    bool vis[N * 105];
    void update(int x){
        tr[x] = tr[ls[x]] + tr[rs[x]];
    }
    void pushdown(int x, int l, int r){
        if(!vis[x] || l == r) return;
        vis[x] = 0;
        int mid = l + r >> 1;
        if(!ls[x]) vis[ls[x] = ++num] = 1, tr[ls[x]] = mid - l + 1, fa[ls[x]] = x;
        if(!rs[x]) vis[rs[x] = ++num] = 1, tr[rs[x]] = r - mid, fa[rs[x]] = x;
    }
    int ins(int &x, int l, int r, int p){
        if(l == r) return x;
        int mid = l + r >> 1;
        pushdown(x, l, r);
        return p <= mid ? ins(ls[x], l, mid, p) : ins(rs[x], mid + 1, r, p);
    }
    int getk(int x, int l, int r, int k){
        if(l == r) return l;
        int mid = l + r >> 1;
        pushdown(x, l, r);
        if(tr[ls[x]] >= k) return getk(ls[x], l, mid, k);
        return getk(rs[x], mid + 1, r, k - tr[ls[x]]);
    }
    int merge(int x, int y, int l, int r){
        if(!x || !y) return x + y;
        pushdown(x, l, r), pushdown(y, l, r);
        if(l == r) assert(1);
        int mid = l + r >> 1;
        ls[x] = merge(ls[x], ls[y], l, mid); if(ls[x]) fa[ls[x]] = x;
        rs[x] = merge(rs[x], rs[y], mid + 1, r); if(rs[x]) fa[rs[x]] = x;
        return update(x), x;
    }
    void split(int &x, int &y, int l, int r, int p){
        if(!x) return;
        pushdown(x, l, r);
        if(p < l) return y = x, x = 0, void();
        if(p >= r) return;
        y = ++num;
        int mid = l + r >> 1;
        split(ls[x], ls[y], l, mid, p);
        split(rs[x], rs[y], mid + 1, r, p);
        if(ls[y]) fa[ls[y]] = y; if(rs[y]) fa[rs[y]] = y;
        update(x), update(y);
    }
    void dfs(int x, int l, int r){
        if(!x) return;
        debug("x:%d [%d,%d] tr:%d vis:%d\n", x, l, r, tr[x], vis[x]);
        if(l == r) return;
        int mid = l + r >> 1;
        dfs(ls[x], l, mid), dfs(rs[x], mid + 1, r);
        if(l == 1 && r == _) debug("======================\n");
    }
}
using namespace sgt;
PII q[N];
int main(){
    read(n), tr[rt[0] = num = 1] = _, mp[1] = 0, vis[1] = 1;
    _rep(i, 1, n){
        read(q[i].fi, q[i].se);
        if(q[i].fi == 3) id[i] = ins(rt[0], 1, _, q[i].se);
    }
    // dfs(rt[0], 1, _);
    _rep(i, 1, n){
        int opt = q[i].fi, x = q[i].se;
        if(opt == 1){
            cnt++, x = min(x, tr[rt[0]]);
            x = getk(rt[0], 1, _, x);
            split(rt[0], rt[cnt], 1, _, x);
            swap(rt[0], rt[cnt]);
            mp[rt[0]] = 0, mp[rt[cnt]] = cnt;
            // dfs(rt[cnt], 1, _);
        }
        if(opt == 2){
            rt[0] = merge(rt[0], rt[x], 1, _);
            mp[rt[0]] = 0;
        }
        if(opt == 3){
            x = id[i];
            while(fa[x]) x = fa[x];
            writeln(mp[x]);
        }
        // debug("fuck rt[0]:\n");
        // dfs(rt[0], 1, _);
    }
    return 0;
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

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

input:

7
1 2
1 4
3 3
2 1
3 2
1 4
3 7

output:

2
0
3

result:

ok 3 number(s): "2 0 3"

Test #2:

score: 0
Accepted
time: 2ms
memory: 15936kb

input:

5
3 6
3 8
1 2
1 5
3 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 15868kb

input:

500
1 17
2 1
3 2
3 17
1 14
1 20
1 15
2 4
1 11
3 72
1 15
3 5
3 79
1 19
2 6
2 2
1 10
3 77
2 5
2 3
3 8
2 7
2 8
3 101
1 16
2 9
3 91
3 61
1 11
3 45
1 9
1 13
1 20
1 19
3 142
2 14
2 11
1 7
3 98
1 3
1 5
1 9
3 119
3 136
1 20
1 7
1 3
1 6
3 106
1 2
2 13
2 17
2 19
3 232
1 19
2 15
3 207
3 264
2 24
1 19
2 12
3 11...

output:

0
0
0
2
0
7
8
0
0
0
0
0
0
0
0
0
0
0
0
0
25
0
0
0
0
0
0
33
0
0
0
0
0
0
0
0
0
0
0
0
52
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
0
0
0
0
0
0
0
0
0
0
0
0
0
92
0
95
0
0
0
0
0
0
0
0
0
0
0
102
0
0
0
0
0
0
0
0
0
0
0
0
0
111
0
0
0
0
0
0
120
0
0
0
0
0
0
0
0
0
0
0
0
0
99
0
0
0
0
0
131
133
0
0
0
0
0
117
0
0
0
0
0...

result:

ok 164 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 16124kb

input:

500
3 1
3 1
3 1
3 1
3 1
1 4412412
1 10247266
1 14616289
3 13925896
1 44094358
2 4
3 16963583
1 29167079
1 71445446
3 121523866
1 9541088
2 6
2 7
3 143236216
2 2
3 156313828
1 33267424
3 100714325
3 15092860
3 89601770
2 8
3 201789970
1 30507527
2 5
1 67021830
3 234973560
1 10823444
1 19147051
1 7218...

output:

0
0
0
0
0
2
3
6
0
0
0
3
0
0
0
0
0
0
13
0
16
17
11
17
0
0
0
0
0
0
0
19
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
0
0
0
45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
57
53
53
53
0
63
0
66
0
0
62
62
72
0
0
53
0
81
69
64
80
53
74
53
81
81
69
90
80
65
95
96
92
0
53
0
101
93
81
103
105
0
102
74
105
74
81
105
93
69
119
1...

result:

ok 174 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 16104kb

input:

500
3 1
3 1
3 1
1 320269189
1 948169162
1 351870928
1 913315720
2 4
1 165426182
1 539661032
3 842094943
3 726768630
1 585756645
1 327182255
3 928037381
3 819034974
3 749190162
3 676969663
2 2
1 802722944
1 848855782
3 227383778
1 725550812
3 892603437
1 451994900
3 470357939
2 1
1 598424975
3 786248...

output:

0
0
0
2
2
2
2
2
2
1
9
9
9
9
0
9
9
9
9
9
0
0
0
0
0
0
0
0
0
0
0
19
0
20
20
24
24
24
24
32
31
0
26
33
38
26
38
32
32
38
38
38
26
38
38
54
38
26
38
38
26
38
38
54
54
54
54
54
65
65
65
67
54
67
54
0
0
70
0
70
72
0
0
0
0
0
0
0
0
0
0
0
78
78
0
0
82
82
0
84
83
84
0
0
87
87
87
87
93
96
96
96
0
0
0
0
0
100
10...

result:

ok 173 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 15936kb

input:

6
3 1
1 3
3 3
1 3
2 2
1 6

output:

0
1

result:

ok 2 number(s): "0 1"

Test #7:

score: 0
Accepted
time: 340ms
memory: 119648kb

input:

500000
3 1
1 5
2 1
3 2
1 10
1 18
1 16
1 15
1 20
2 2
3 8
3 4
2 6
2 5
2 3
1 13
3 16
2 7
2 4
3 34
1 12
1 11
2 8
3 18
3 97
1 7
3 128
3 13
2 9
2 10
3 81
3 48
1 5
2 11
1 4
2 12
1 5
1 15
1 13
2 14
2 15
1 3
1 6
2 16
3 141
2 17
1 6
2 13
2 18
1 10
1 12
3 102
2 20
1 11
3 86
1 7
3 176
2 21
1 5
3 92
1 14
2 22
1 ...

output:

0
0
0
0
0
0
9
0
0
9
0
0
0
0
0
0
0
0
0
0
39
0
0
0
0
0
39
0
0
0
0
0
0
35
0
49
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
86
0
0
0
0
0
0
0
0
0
94
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
127
134
128
0
0
0
0
0
128
0
0
0
0
0
133
0
0
0
0
0
0
0
0
...

result:

ok 167358 numbers

Test #8:

score: 0
Accepted
time: 301ms
memory: 149952kb

input:

500000
3 1
1 34999032
2 1
3 20479366
3 16132210
3 10950706
3 27656988
3 18181558
3 20096893
1 83795773
3 113805204
3 115628116
1 42488647
1 42211622
2 3
1 92268056
2 2
1 80060142
2 4
1 49696107
3 299966231
3 365132652
1 46139635
1 64375123
2 8
3 39930760
1 14908781
3 210153892
1 85648326
3 568835561...

output:

0
0
0
0
0
0
0
0
0
0
0
6
5
0
5
6
0
0
0
0
0
0
18
0
6
0
19
18
18
19
0
0
0
23
0
21
0
24
0
28
0
0
0
34
0
37
38
39
0
0
0
0
0
0
43
0
0
49
48
43
0
0
43
48
0
0
55
0
55
58
0
0
0
0
0
0
0
0
68
0
0
0
0
0
0
0
77
72
86
75
0
72
0
82
0
0
0
0
0
92
0
106
0
106
92
0
0
0
0
0
0
0
0
0
0
0
0
126
0
0
0
0
0
130
0
0
0
138
0
0...

result:

ok 166515 numbers

Test #9:

score: 0
Accepted
time: 229ms
memory: 117216kb

input:

500000
3 1
3 1
3 1
1 85593529
3 57891556
2 1
3 38559908
1 727251945
1 815334095
1 988926819
3 107155104
1 724052442
3 63908582
2 5
2 4
1 84610655
2 2
3 2423402
3 853118582
1 448879846
2 6
2 3
1 815614446
2 8
1 674635945
2 7
1 46140898
3 820338862
2 10
1 692524546
2 11
1 625079933
1 482471788
3 44351...

output:

0
0
0
1
0
2
2
0
3
9
12
9
9
9
21
9
21
21
0
0
0
21
27
27
30
28
30
28
0
28
38
42
28
43
43
38
43
45
45
45
51
47
47
45
47
51
51
45
51
68
51
51
45
45
68
45
47
45
47
45
45
51
80
0
81
81
81
81
81
81
0
0
0
0
84
84
85
84
85
84
84
84
84
84
0
0
0
95
95
95
95
95
99
98
99
95
98
95
98
98
98
95
95
98
95
103
111
111...

result:

ok 166286 numbers

Test #10:

score: 0
Accepted
time: 41ms
memory: 16184kb

input:

500000
1 39567744
1 957918384
1 896336073
1 302217145
1 328404139
1 984894105
1 428308004
1 67268263
1 619517065
1 186724562
1 165376000
1 253795867
1 721330183
1 433623064
1 20169195
1 288503667
1 791272786
1 526657641
1 638212274
1 501209932
1 320898519
1 288747265
1 581193313
1 497930627
1 423401...

output:

result:

ok 0 number(s): ""

Test #11:

score: 0
Accepted
time: 516ms
memory: 501760kb

input:

500000
1 198
1 267
1 305
1 955
2 3
1 242
1 854
3 1322
1 337
1 830
1 838
1 703
1 81
1 667
1 591
1 152
1 308
1 326
1 237
1 362
1 199
1 252
1 910
3 2543
2 12
1 90
1 646
1 444
1 520
1 206
1 283
1 207
1 793
1 236
1 681
1 21
1 470
1 625
1 326
2 25
1 916
1 922
1 614
1 317
1 399
1 508
3 12977
1 368
1 558
1 ...

output:

4
7
33
46
57
57
104
10
0
43
0
50
137
162
169
220
73
108
44
86
154
41
213
192
0
125
331
52
472
58
165
558
547
0
430
234
628
330
625
54
409
703
0
613
498
258
702
282
418
346
171
667
0
650
722
9
739
88
471
542
340
253
401
479
490
399
1082
817
1121
449
807
1121
641
797
20
1327
351
810
1337
1208
783
620
...

result:

ok 25227 numbers

Test #12:

score: 0
Accepted
time: 531ms
memory: 250496kb

input:

500000
1 249
1 435
2 2
1 48
2 3
2 1
1 510
2 4
1 626
2 5
1 831
3 1996
1 237
1 759
2 8
3 2585
1 155
1 601
1 665
1 803
2 9
2 10
2 6
2 7
1 114
1 605
1 895
1 155
2 16
1 625
2 13
2 17
1 242
1 15
3 3636
2 11
2 14
3 3530
3 6827
2 12
1 356
1 615
1 148
1 331
3 785
1 275
1 794
1 596
1 495
2 23
1 140
2 20
1 238...

output:

0
0
0
0
0
15
0
0
26
0
0
0
0
0
94
0
0
113
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
117
162
0
213
194
0
117
0
0
0
249
211
0
0
0
0
0
0
287
0
0
290
0
267
0
166
0
0
243
349
0
266
327
0
338
338
0
0
0
336
0
0
0
0
0
0
0
0
401
0
0
375
416
371
343
258
0
0
0
0
0
0
0
0
462
0
0
0
0
462
0
0
452
0
0
0
0
411
0
456
0
0
0
498...

result:

ok 49640 numbers

Test #13:

score: 0
Accepted
time: 200ms
memory: 81160kb

input:

500000
1 325663181
1 341421661
2 1
2 2
1 798695561
1 789604791
2 3
1 752705846
1 271837520
1 2324300
1 156465725
1 552978643
1 704305136
3 708781692
1 538026101
1 554055497
1 551799143
1 928267539
1 162992249
1 178671365
1 41327601
1 34105375
3 583284520
2 4
1 335357707
2 18
2 13
1 351743555
2 11
1 ...

output:

5
5
6
5
5
5
5
5
42
67
42
67
66
82
82
82
0
82
82
94
99
94
82
114
82
94
82
82
82
67
94
94
94
0
67
0
94
148
149
67
149
149
149
149
149
149
149
158
158
149
67
0
213
158
214
214
214
214
214
213
158
214
158
232
265
264
158
158
265
264
305
265
280
232
265
264
265
265
331
265
265
264
325
264
264
331
295
264...

result:

ok 49895 numbers

Test #14:

score: 0
Accepted
time: 578ms
memory: 327584kb

input:

500000
3 1
1 208
1 44
1 519
1 107
3 587
3 745
3 158
3 364
3 120
1 232
1 101
1 879
3 517
3 882
3 1383
1 877
3 876
3 2890
1 597
1 938
3 221
1 882
1 423
3 4211
1 954
1 849
1 159
3 5130
3 2488
1 186
3 6193
1 211
1 783
1 476
1 411
1 469
3 5038
3 3069
1 145
2 4
3 8960
3 4781
1 216
3 9895
1 863
1 740
1 70
...

output:

0
3
3
1
3
1
3
5
7
4
8
2
10
11
8
13
11
9
19
11
21
9
7
11
10
7
3
11
25
18
9
19
28
28
25
34
38
31
29
24
11
14
34
21
42
32
21
28
11
7
47
7
11
27
37
55
10
50
49
52
39
8
21
55
64
38
3
34
10
65
32
69
31
61
36
5
10
10
7
34
0
70
79
55
10
1
27
19
50
45
12
38
63
34
9
65
0
72
24
75
68
27
25
66
62
57
84
50
24
80...

result:

ok 224721 numbers

Test #15:

score: 0
Accepted
time: 389ms
memory: 162864kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 495045 numbers

Test #16:

score: 0
Accepted
time: 560ms
memory: 166640kb

input:

500000
1 398
1 645
2 2
1 985
2 3
2 1
1 240
2 4
1 856
2 5
1 469
1 729
1 298
2 7
2 8
2 6
1 944
2 9
1 490
2 10
1 404
1 599
2 11
1 693
1 791
1 762
1 73
2 14
2 12
1 904
2 15
2 17
1 627
2 16
1 200
1 170
2 20
1 611
2 13
1 879
1 270
2 18
2 23
1 575
2 19
1 377
2 25
2 24
2 22
2 21
1 971
2 26
1 118
1 224
2 28
...

output:

45
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
497
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 9965 numbers

Test #17:

score: 0
Accepted
time: 479ms
memory: 206868kb

input:

500000
3 863503832
3 285813354
3 414051174
3 97666985
3 466272422
3 448257369
3 956137762
3 387839447
3 504996933
3 971922171
3 737655581
3 914663293
3 431235168
3 598801556
3 197441204
1 9085
3 18435039
1 28953
3 240290602
3 660593544
3 278294539
3 760061094
3 947453399
3 182070243
3 222738570
3 93...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 460003 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 13948kb

input:

5
1 1000000000
2 1
3 1000000000
1 1000000000
3 1000000000

output:

0
2

result:

ok 2 number(s): "0 2"

Test #19:

score: 0
Accepted
time: 2ms
memory: 16008kb

input:

1
3 11451419

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 487ms
memory: 245128kb

input:

500000
1 469
1 27403
1 8011
1 3666
3 431375941
1 5586
1 2876
1 911
1 8549
1 5022
1 11870
1 13676
1 14008
1 7714
1 5558
1 23433
1 5420
1 6330
1 1234
1 21150
1 15806
1 10289
1 638
1 1291
1 5427
1 304
1 7921
1 5709
1 586
1 3002
1 12144
1 5379
1 21367
1 10314
1 15571
1 21493
1 2691
1 7216
1 762
1 7791
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
324
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2181
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1723
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
54
0
0
0...

result:

ok 20003 numbers

Test #21:

score: 0
Accepted
time: 473ms
memory: 242356kb

input:

500000
1 2869
1 11476
1 2081
1 3225
1 6496
1 11473
1 4014
1 3439
1 13952
1 4133
1 4627
1 3486
1 24176
1 1103
1 15107
1 19628
1 1634
1 604
1 1669
1 12717
1 5305
1 17384
1 13159
1 574
1 11642
1 876
1 23211
1 26850
1 9274
1 3403
1 4044
1 5642
1 6203
1 1352
1 5604
1 969
1 4262
1 29813
1 11471
1 3397
1 3...

output:

24734
167977
249999

result:

ok 3 number(s): "24734 167977 249999"

Test #22:

score: 0
Accepted
time: 608ms
memory: 277204kb

input:

500000
1 471049
3 210537770
3 174642262
3 409419351
1 117066
1 33053
1 13142
3 181598847
1 129357
1 37381
1 197686
3 478570811
1 58776
1 14683
1 151018
3 51491818
1 138638
1 85547
1 188477
1 757
1 3848
1 53283
1 77145
1 29393
1 91077
1 132182
3 167622476
1 110618
1 29202
1 133185
1 33985
3 436250120...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
82
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
106
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
87
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 200002 numbers

Test #23:

score: 0
Accepted
time: 661ms
memory: 313464kb

input:

500000
1 159000
1 13720
1 6590
1 59370
1 220632
1 513661
1 609
1 104291
1 3779
1 56248
1 189477
1 150404
1 10964
1 77315
1 135285
1 141171
1 16173
1 180444
1 97299
1 157409
1 14352
1 25243
1 10016
1 180301
1 32208
1 91019
1 105454
1 59531
1 501
1 139128
1 104096
1 4905
1 708069
1 213704
1 28070
1 31...

output:

0
0
0
0
0
0
0
0
255
0
0
0
0
299
0
590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
361
0
0
0
0
0
956
0
0
1736
1063
0
0
1392
0
2222
0
0
0
1418
0
0
1744
2445
0
2488
0
0
681
186
0
0
329
0
2573
0
438
0
0
0
0
0
1000
0
2463
0
1488
0
0
0
1533
3115
3493
0
0
3494
0
590
0
0
0
0
0
3392
0
709
0
2856
0
0
3898
266
0
0
0
2947
2867...

result:

ok 10002 numbers

Test #24:

score: 0
Accepted
time: 404ms
memory: 417208kb

input:

500000
1 7530
1 5375
1 1583
1 10219
1 1563
1 1637
1 9573
1 1527
1 519
1 907
1 3795
1 6745
1 3936
1 4545
1 2291
1 599
1 617
1 3527
1 3061
1 1749
1 1944
1 4604
1 122
1 7561
1 1225
1 350
1 605
1 7258
1 242
1 428
1 1349
1 519
1 4304
1 1632
1 1073
1 1218
1 716
1 3848
1 538
1 3270
1 2546
1 1623
1 3093
1 2...

output:

0
0
0
0
0
0
53265
52394
0
0
0
0
0
0
65065
92942
0
0
23935
0
117540
0
0
169499
0
0
20825
97207
4208
0
0
94282
80833
0
0
190036
0
49502
0
0
141569
73882
0
0
28789
0
391
99126
255997
207625
11835
38585
276369
27212
141749
105272
143287
206441
59980
100724
182350
300990
0
221882
13051
187940
143694
1064...

result:

ok 101 numbers

Test #25:

score: 0
Accepted
time: 391ms
memory: 422844kb

input:

500000
1 2652
1 534
1 2173
1 350
1 776
1 9854
1 1849
1 5884
1 2083
1 2706
1 7416
1 379
1 2734
1 5024
1 108
1 835
1 6766
1 2331
1 3167
1 7043
1 4438
1 88
1 715
1 386
1 7707
1 12583
1 1037
1 361
1 2641
1 1840
1 2241
1 5368
1 5803
1 2963
1 2002
1 1577
1 2601
1 931
1 3026
1 1192
1 717
1 80
1 3971
1 36
1...

output:

59154
0
0
215216
242549
177051

result:

ok 6 numbers

Test #26:

score: 0
Accepted
time: 380ms
memory: 177980kb

input:

500000
1 2
1 2
3 2
3 5
2 1
1 4
1 9
2 3
1 6
1 3
2 5
1 8
1 1
2 7
1 9
1 1
2 9
1 14
1 1
3 25
2 11
1 15
1 1
2 13
1 16
1 3
2 15
1 20
1 4
2 17
1 23
1 1
2 19
1 27
1 1
2 21
1 31
1 2
2 23
3 86
1 35
1 1
2 25
1 40
3 526
1 1
2 27
1 41
1 5
3 499
2 29
1 45
1 1
2 31
1 46
1 6
2 33
1 53
1 1
2 35
1 55
1 1
2 37
3 290
1...

output:

1
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
310
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
859
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 50000 numbers

Test #27:

score: 0
Accepted
time: 381ms
memory: 177672kb

input:

500000
1 1
1 1
2 1
1 2
1 1
2 3
1 5
1 1
3 2
2 5
1 6
3 22
3 29
1 3
3 4
2 7
3 31
1 7
1 2
3 7
2 9
1 8
3 39
1 1
2 11
3 13
1 11
1 1
2 13
1 13
1 1
2 15
3 65
1 14
1 3
2 17
1 17
1 3
3 15
2 19
1 18
1 1
2 21
1 21
1 2
3 256
2 23
1 22
1 1
3 299
3 165
2 25
1 23
1 1
2 27
3 133
1 24
1 1
3 195
2 29
1 26
1 3
2 31
1 2...

output:

2
0
0
4
0
9
0
0
0
10
0
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
42
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 375ms
memory: 158756kb

input:

500000
1 1
1 1
3 82936
2 1
1 2
1 1
2 3
1 3
1 1
2 5
1 4
1 1
2 7
1 5
3 1415
1 1
2 9
1 6
3 45737
3 103035
3 74547
1 1
3 66256
3 8539
2 11
1 7
3 127811
1 1
3 119207
2 13
1 8
3 8066
1 1
2 15
1 9
1 1
2 17
1 10
1 1
2 19
1 11
1 1
3 30227
2 21
1 12
1 1
2 23
1 13
3 120832
1 1
2 25
1 14
1 1
3 68095
3 98568
2 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 106787 numbers

Test #29:

score: 0
Accepted
time: 404ms
memory: 186892kb

input:

500000
1 1
1 1
2 1
1 2
1 1
2 3
1 3
1 1
2 5
1 4
1 1
2 7
3 81250
1 5
1 1
2 9
1 6
1 1
2 11
1 7
1 1
2 13
1 8
1 1
2 15
1 9
1 1
2 17
1 10
1 1
2 19
1 11
1 1
2 21
1 12
3 32637
1 1
2 23
1 13
1 1
2 25
1 14
1 1
2 27
1 15
1 1
3 105337
2 29
1 16
1 1
2 31
1 17
1 1
2 33
1 18
1 1
2 35
1 19
1 1
2 37
1 20
1 1
2 39
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
250
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 19985 numbers

Test #30:

score: 0
Accepted
time: 292ms
memory: 102696kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 499516 numbers

Test #31:

score: 0
Accepted
time: 454ms
memory: 186996kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
1 62492
3 48564
3 53972
3 58895
3 22522
3 51135
3 41461
3 55004
3 28281
3 437...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 489886 numbers

Test #32:

score: 0
Accepted
time: 460ms
memory: 213176kb

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
1 18450
3 14728
3 16406
3 11557
3 17169
3 11487
3 15297
3 17123
3 11132
3 18023
3 1430
3 12177
1 86902
1 17254
3 59286
3 3672
3 35650
3 99347
3 7143
3 110044
3 26590
3 76721
3 52658
3 46320
3 90002
3 102691
3 108407
3 70488
3 105068
3 99678
1 93326
3 138355
3 10002...

output:

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

result:

ok 474862 numbers

Test #33:

score: 0
Accepted
time: 510ms
memory: 620872kb

input:

500000
1 2775
1 3338
1 3532
1 3689
1 2814
1 1591
1 3770
1 2339
1 848
1 158
1 1844
1 3903
1 3902
1 1600
1 2346
1 3614
1 57
1 2236
1 1774
1 2145
1 3570
1 3317
1 1681
1 2856
1 1275
1 3020
1 676
1 2294
1 771
1 3264
1 3159
1 2506
1 2173
1 2805
1 1531
1 3494
1 3321
1 1065
1 3651
1 2284
1 3176
1 3743
1 990...

output:

3231
8303
7601
11560
9952
26443
10762
4567
37316
29847
50832
14434
20849
43582
6175
88876
17243
92915
63273
131214
87285
126463
28663
52183
84363
123912
71654
88103
133433
113191
147394
59330
164450
106191
106534
99764
181942
258915
63070
37034
263828
200313
231186
205406
83878
140715
32414
99313
56...

result:

ok 64 numbers

Test #34:

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

input:

500000
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3 1
3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 500000 numbers

Test #35:

score: 0
Accepted
time: 65ms
memory: 16748kb

input:

500000
1 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 10000...

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 499999 numbers

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-05 04:36:21 | 开源项目