QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#771345	#8672. 排队	user10086	100 ✓	1241ms	59148kb	C++23	2.5kb	2024-11-22 11:58:02	2024-11-22 11:58:03

Judging History

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

[2024-11-22 11:58:03]
评测

测评结果：100
用时：1241ms
内存：59148kb

查看

[2024-11-22 11:58:02]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int l[N], r[N], a[N];

struct Q
{
	int l, r, ans, id;
}qry[N];

namespace tr
{
	int n, mn[N << 2], mx[N << 2], tadd[N << 2];

	void pushup(int i)
	{
		mn[i] = min(mn[i << 1], mn[i << 1 | 1]), mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
	}
	
	void apply(int i, int dadd)
	{
		mn[i] += dadd, mx[i] += dadd, tadd[i] += dadd;
	}
	
	void pushdown(int i)
	{
		if (!tadd[i]) return;
		apply(i << 1, tadd[i]), apply(i << 1 | 1, tadd[i]);
		tadd[i] = 0;
	}

	void build(int *a, int i = 1, int li = 1, int ri = n)
	{
		if (li == ri)
		{
			mn[i] = mx[i] = a[li];
			return;
		}
		int mid = (li + ri) >> 1;
		build(a, i << 1, li, mid), build(a, i << 1 | 1, mid + 1, ri);
		pushup(i);
	}
	
	void init(int sz)
	{
		n = sz;
	}
	
	void add(int l, int r, int i = 1, int li = 1, int ri = n)
	{
		if (l <= li && ri <= r) return apply(i, 1);
		pushdown(i);
		int mid = (li + ri) >> 1;
		if (l <= mid) add(l, r, i << 1, li, mid);
		if (r > mid) add(l, r, i << 1 | 1, mid + 1, ri);
		pushup(i);
	}
	
	int qfirst(int v, int i = 1, int li = 1, int ri = n)
	{
		// first <= v
		if (li == ri) return mx[i] <= v ? li : n + 1;
		pushdown(i);
		int mid = (li + ri) >> 1;
		if (mn[i << 1] <= v) return qfirst(v, i << 1, li, mid);
		else return qfirst(v, i << 1 | 1, mid + 1, ri);
	}
	
	int qlast(int v, int i = 1, int li = 1, int ri = n)
	{
		// last >= v
		if (li == ri) return mn[i] >= v ? li : -1;
		pushdown(i);
		int mid = (li + ri) >> 1;
		if (mx[i << 1 | 1] >= v) return qlast(v, i << 1 | 1, mid + 1, ri);
		else return qlast(v, i << 1, li, mid);
	}
	
	int qval(int pos, int i = 1, int li = 1, int ri = n)
	{
		if (li == ri) return mn[i];
		pushdown(i);
		int mid = (li + ri) >> 1;
		if (pos <= mid) return qval(pos, i << 1, li, mid);
		else return qval(pos, i << 1 | 1, mid + 1, ri);
	}
}

signed main()
{
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
	for (int i = 1; i <= q; i++) cin >> qry[i].l >> qry[i].r, qry[i].id = i;
	tr::init(n);
	sort(qry + 1, qry + 1 + q, [](Q q1, Q q2) { return q1.r < q2.r; });
	for (int i = 1, id = 1; i <= n; i++)
	{
		int lp = tr::qfirst(r[i]), rp = min(i, tr::qlast(l[i]));
		if (lp <= rp) tr::add(lp, rp);
		while (id <= q && qry[id].r == i)
		{
			qry[id].ans = tr::qval(qry[id].l);
			id++;
		}
	}
	sort(qry + 1, qry + 1 + q, [](Q q1, Q q2) { return q1.id < q2.id; });
	for (int i = 1; i <= q; i++) cout << qry[i].ans << '\n';
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 0ms

memory: 9728kb

input:

output:

1
3
1

result:

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

Test #2:

score: 10

Accepted

time: 6ms

memory: 9988kb

input:

output:

result:

ok 5000 numbers

Test #3:

score: 10

Accepted

time: 6ms

memory: 10032kb

input:

output:

result:

ok 5000 numbers

Test #4:

score: 10

Accepted

time: 6ms

memory: 9988kb

input:

output:

result:

ok 5000 numbers

Test #5:

score: 10

Accepted

time: 0ms

memory: 9964kb

input:

output:

result:

ok 5000 numbers

Test #6:

score: 10

Accepted

time: 6ms

memory: 9840kb

input:

output:

result:

ok 5000 numbers

Test #7:

score: 10

Accepted

time: 3ms

memory: 10060kb

input:

output:

result:

ok 5000 numbers

Test #8:

score: 10

Accepted

time: 3ms

memory: 11968kb

input:

output:

result:

ok 5000 numbers

Test #9:

score: 10

Accepted

time: 6ms

memory: 9932kb

input:

output:

result:

ok 5000 numbers

Test #10:

score: 10

Accepted

time: 3ms

memory: 9972kb

input:

output:

result:

ok 5000 numbers

Test #11:

score: 10

Accepted

time: 5ms

memory: 10000kb

input:

output:

result:

ok 5000 numbers

Subtask #2:

score: 15

Accepted

Test #12:

score: 15

Accepted

time: 168ms

memory: 21552kb

input:

200000 200000
3 6
3 3
6 10
1 7
2 7
6 9
4 6
3 4
0 8
0 6
3 5
3 4
1 8
7 8
4 5
0 3
1 5
2 9
1 2
1 2
3 4
5 7
6 10
3 9
4 7
1 6
2 6
1 7
2 5
1 7
6 8
1 1
0 7
7 8
0 9
1 7
3 8
3 7
1 2
4 8
5 6
0 6
5 6
2 7
2 6
0 6
0 6
1 7
2 5
0 3
0 3
7 10
3 8
0 2
3 4
3 7
4 9
0 6
4 7
2 6
8 10
2 10
4 10
3 3
2 6
4 5
3 9
1 8
1 2
2 9
...

output:

result:

ok 200000 numbers

Test #13:

score: 15

Accepted

time: 170ms

memory: 21796kb

input:

200000 200000
5 45
27 99
7 23
51 88
16 62
10 24
16 80
43 70
12 45
35 55
6 99
77 91
40 82
66 99
30 47
18 80
9 36
4 12
26 51
37 64
39 52
2 11
2 69
57 81
15 98
8 36
19 27
32 34
35 97
22 23
15 89
53 77
2 89
25 55
25 90
4 91
13 77
37 65
67 89
8 52
20 58
10 18
31 81
35 59
41 56
71 74
18 61
56 77
51 74
40 ...

output:

result:

ok 200000 numbers

Test #14:

score: 15

Accepted

time: 182ms

memory: 23068kb

input:

200000 200000
193 894
142 229
346 553
197 496
389 718
370 600
650 853
476 695
764 767
220 571
238 714
516 700
137 692
1 293
835 962
34 536
208 482
148 225
377 804
75 864
277 925
278 864
296 647
390 757
179 283
338 602
571 746
447 852
315 365
7 390
634 689
76 239
16 60
244 388
385 822
451 836
301 373...

output:

result:

ok 200000 numbers

Test #15:

score: 15

Accepted

time: 183ms

memory: 20272kb

input:

200000 200000
3145 7698
6037 6154
6483 6707
6834 7442
7373 9621
5166 8045
7346 8938
2235 5518
2240 4134
586 3188
3845 8054
1258 5380
2409 2631
3360 5706
19 2771
1925 9642
6687 8264
4305 8055
2844 5474
2282 7810
1738 4706
1462 7466
17 6282
2481 6022
2363 2987
3633 4157
1460 2634
4866 8159
3154 5079
2...

output:

result:

ok 200000 numbers

Test #16:

score: 15

Accepted

time: 167ms

memory: 16660kb

input:

200000 200000
15540 44932
12196 33126
776 23774
35673 42863
31231 44618
16521 19781
8467 9747
5319 42216
13940 21955
3389 6981
22 11576
15248 17307
5734 35942
12762 45217
30349 47977
8869 11242
11199 25942
3415 10196
20104 40771
8813 28517
29726 34188
13420 13731
17526 30474
1033 44930
3143 10541
46...

output:

result:

ok 200000 numbers

Test #17:

score: 15

Accepted

time: 180ms

memory: 23096kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
...

output:

result:

ok 200000 numbers

Test #18:

score: 15

Accepted

time: 183ms

memory: 20816kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 0
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 0
0 27
0 28
0 29
0 30
0 0
0 32
0 33
0 34
0 35
0 36
0 0
0 0
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 0
0 58
0 59
0 60
0...

output:

result:

ok 200000 numbers

Test #19:

score: 15

Accepted

time: 191ms

memory: 23364kb

input:

200000 200000
45 200000
27 200000
7 200000
51 200000
16 200000
10 200000
16 200000
43 200000
12 200000
35 200000
6 200000
77 200000
40 200000
66 200000
30 200000
18 200000
36 200000
12 200000
26 200000
37 200000
39 200000
11 200000
69 200000
57 200000
15 200000
8 200000
19 200000
32 200000
35 200000...

output:

result:

ok 200000 numbers

Test #20:

score: 15

Accepted

time: 191ms

memory: 24616kb

input:

200000 200000
6 200000
3 200000
6 200000
7 200000
2 200000
9 200000
4 200000
3 200000
0 200000
6 200000
3 200000
3 200000
1 200000
8 200000
4 200000
3 200000
5 200000
2 200000
2 200000
2 200000
4 200000
5 200000
6 200000
3 200000
7 200000
1 200000
2 200000
7 200000
2 200000
1 200000
6 200000
1 20000...

output:

result:

ok 200000 numbers

Test #21:

score: 15

Accepted

time: 155ms

memory: 18284kb

input:

200000 200000
17611 69131
59430 76978
15340 23731
45422 61357
24684 32905
12111 30945
3173 53122
1908 18775
21868 25563
43076 69772
23316 73134
37315 71711
16622 29769
5311 27384
7573 9838
45306 81042
21408 85530
32497 55253
12816 72989
13973 55180
2256 48643
39562 81719
47954 61844
8166 64533
5302 ...

output:

result:

ok 200000 numbers

Subtask #3:

score: 15

Accepted

Test #22:

score: 15

Accepted

time: 212ms

memory: 22724kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 0
0 9
0 10
0 0
0 0
0 13
0 14
0 0
0 16
0 17
0 18
0 19
0 0
0 21
0 22
0 23
0 0
0 0
0 0
0 0
0 28
0 0
0 30
0 31
0 32
0 33
0 34
0 35
0 0
0 0
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 0
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 0
0 59
0 60
0 0
0 0
...

output:

result:

ok 200000 numbers

Test #23:

score: 15

Accepted

time: 220ms

memory: 25100kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 0
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 0
0 27
0 28
0 29
0 30
0 0
0 32
0 33
0 34
0 35
0 36
0 0
0 0
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 0
0 58
0 59
0 60
0...

output:

result:

ok 200000 numbers

Test #24:

score: 15

Accepted

time: 217ms

memory: 24652kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15
0 16
0 17
0 18
0 19
0 20
0 21
0 22
0 23
0 24
0 25
0 26
0 27
0 28
0 29
0 30
0 31
0 32
0 33
0 34
0 35
0 36
0 37
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 47
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 58
0 59
...

output:

result:

ok 200000 numbers

Test #25:

score: 15

Accepted

time: 217ms

memory: 22576kb

input:

200000 200000
0 5
0 99
0 23
0 88
0 62
0 24
0 80
0 70
0 45
0 55
0 99
0 91
0 82
0 99
0 47
0 80
0 9
0 4
0 51
0 64
0 52
0 2
0 2
0 81
0 98
0 36
0 27
0 34
0 97
0 22
0 89
0 77
0 89
0 25
0 90
0 91
0 77
0 37
0 89
0 52
0 58
0 18
0 81
0 35
0 56
0 71
0 18
0 56
0 74
0 40
0 76
0 47
0 87
0 11
0 81
0 48
0 59
0 17
0...

output:

result:

ok 200000 numbers

Test #26:

score: 15

Accepted

time: 230ms

memory: 20928kb

input:

200000 200000
0 193
0 229
0 553
0 197
0 718
0 370
0 853
0 695
0 764
0 571
0 714
0 700
0 692
0 293
0 962
0 536
0 482
0 148
0 804
0 864
0 925
0 864
0 296
0 757
0 283
0 338
0 746
0 447
0 365
0 390
0 689
0 239
0 60
0 388
0 822
0 836
0 373
0 703
0 107
0 894
0 468
0 125
0 851
0 568
0 914
0 391
0 759
0 66
...

output:

result:

ok 200000 numbers

Test #27:

score: 15

Accepted

time: 247ms

memory: 23532kb

input:

200000 200000
0 7698
0 6154
0 6707
0 7442
0 9621
0 8045
0 8938
0 5518
0 4134
0 3188
0 8054
0 5380
0 2409
0 3360
0 2771
0 9642
0 8264
0 4305
0 2844
0 7810
0 4706
0 1462
0 6282
0 2481
0 2987
0 3633
0 2634
0 4866
0 5079
0 2325
0 4394
0 8361
0 322
0 2614
0 7668
0 9067
0 452
0 2834
0 3340
0 2193
0 4070
0...

output:

result:

ok 200000 numbers

Test #28:

score: 15

Accepted

time: 269ms

memory: 24372kb

input:

200000 200000
0 44932
0 12196
0 776
0 35673
0 44618
0 16521
0 9747
0 42216
0 21955
0 3389
0 22
0 15248
0 5734
0 45217
0 47977
0 8869
0 25942
0 3415
0 40771
0 28517
0 29726
0 13420
0 30474
0 44930
0 10541
0 4648
0 26903
0 19507
0 2998
0 24757
0 10645
0 47790
0 25779
0 41892
0 37322
0 34913
0 36562
0 ...

output:

result:

ok 200000 numbers

Test #29:

score: 15

Accepted

time: 235ms

memory: 21708kb

input:

200000 200000
0 17611
0 59430
0 23731
0 61357
0 32905
0 30945
0 53122
0 18775
0 25563
0 43076
0 23316
0 71711
0 16622
0 27384
0 9838
0 81042
0 85530
0 32497
0 12816
0 55180
0 2256
0 81719
0 61844
0 64533
0 5302
0 33711
0 18419
0 98385
0 48813
0 58297
0 63392
0 29066
0 12542
0 14198
0 27695
0 23110
0...

output:

result:

ok 200000 numbers

Test #30:

score: 15

Accepted

time: 205ms

memory: 21916kb

input:

200000 200000
0 19
0 50
0 16
0 8
0 27
0 35
0 43
0 42
0 8
0 45
0 39
0 16
0 23
0 29
0 10
0 10
0 50
0 23
0 50
0 45
0 16
0 17
0 30
0 17
0 35
0 50
0 2
0 15
0 33
0 41
0 38
0 12
0 2
0 5
0 37
0 11
0 26
0 35
0 25
0 12
0 38
0 28
0 5
0 46
0 46
0 39
0 26
0 36
0 22
0 9
0 1
0 45
0 36
0 6
0 15
0 31
0 2
0 3
0 0
0 4...

output:

result:

ok 200000 numbers

Test #31:

score: 15

Accepted

time: 192ms

memory: 21664kb

input:

200000 200000
0 3
0 3
0 10
0 1
0 7
0 6
0 6
0 4
0 8
0 0
0 5
0 4
0 8
0 7
0 5
0 0
0 1
0 9
0 1
0 1
0 3
0 7
0 10
0 9
0 4
0 6
0 6
0 1
0 5
0 7
0 8
0 1
0 0
0 8
0 9
0 7
0 8
0 7
0 2
0 8
0 6
0 6
0 5
0 7
0 2
0 0
0 6
0 7
0 5
0 3
0 3
0 10
0 3
0 0
0 3
0 3
0 9
0 0
0 7
0 2
0 10
0 10
0 10
0 3
0 2
0 5
0 9
0 1
0 1
0 9
...

output:

result:

ok 200000 numbers

Subtask #4:

score: 15

Accepted

Test #32:

score: 15

Accepted

time: 231ms

memory: 23456kb

input:

200000 200000
0 200000
1 200000
1 200000
0 200000
0 200000
1 200000
1 200000
1 200000
0 200000
1 200000
0 200000
0 200000
1 200000
0 200000
0 200000
0 200000
0 200000
1 200000
0 200000
0 200000
1 200000
0 200000
1 200000
1 200000
1 200000
1 200000
0 200000
0 200000
1 200000
2 200000
1 200000
2 20000...

output:

result:

ok 200000 numbers

Test #33:

score: 15

Accepted

time: 219ms

memory: 22804kb

input:

200000 200000
5 200000
0 200000
1 200000
0 200000
2 200000
1 200000
0 200000
3 200000
4 200000
1 200000
0 200000
2 200000
1 200000
0 200000
0 200000
5 200000
2 200000
0 200000
2 200000
2 200000
0 200000
1 200000
3 200000
4 200000
2 200000
0 200000
5 200000
0 200000
3 200000
0 200000
0 200000
5 20000...

output:

result:

ok 200000 numbers

Test #34:

score: 15

Accepted

time: 227ms

memory: 24500kb

input:

200000 200000
6 200000
3 200000
6 200000
7 200000
2 200000
9 200000
4 200000
3 200000
0 200000
6 200000
3 200000
3 200000
1 200000
8 200000
4 200000
3 200000
5 200000
2 200000
2 200000
2 200000
4 200000
5 200000
6 200000
3 200000
7 200000
1 200000
2 200000
7 200000
2 200000
1 200000
6 200000
1 20000...

output:

result:

ok 200000 numbers

Test #35:

score: 15

Accepted

time: 231ms

memory: 21668kb

input:

200000 200000
45 200000
27 200000
7 200000
51 200000
16 200000
10 200000
16 200000
43 200000
12 200000
35 200000
6 200000
77 200000
40 200000
66 200000
30 200000
18 200000
36 200000
12 200000
26 200000
37 200000
39 200000
11 200000
69 200000
57 200000
15 200000
8 200000
19 200000
32 200000
35 200000...

output:

result:

ok 200000 numbers

Test #36:

score: 15

Accepted

time: 233ms

memory: 20016kb

input:

200000 200000
894 200000
142 200000
346 200000
496 200000
389 200000
600 200000
650 200000
476 200000
767 200000
220 200000
238 200000
516 200000
137 200000
1 200000
835 200000
34 200000
208 200000
225 200000
377 200000
75 200000
277 200000
278 200000
647 200000
390 200000
179 200000
602 200000
571 ...

output:

result:

ok 200000 numbers

Test #37:

score: 15

Accepted

time: 189ms

memory: 25008kb

input:

200000 200000
30 200000
9 200000
18 200000
24 200000
68 200000
54 200000
26 200000
3 200000
42 200000
32 200000
27 200000
58 200000
1 200000
34 200000
16 200000
61 200000
11 200000
25 200000
69 200000
48 200000
1 200000
11 200000
51 200000
46 200000
45 200000
48 200000
8 200000
11 200000
76 200000
1...

output:

result:

ok 200000 numbers

Test #38:

score: 15

Accepted

time: 183ms

memory: 20992kb

input:

200000 200000
4 200000
3 200000
5 200000
9 200000
3 200000
5 200000
3 200000
4 200000
1 200000
7 200000
5 200000
2 200000
2 200000
5 200000
7 200000
0 200000
2 200000
1 200000
6 200000
7 200000
3 200000
4 200000
5 200000
2 200000
2 200000
6 200000
2 200000
8 200000
8 200000
2 200000
2 200000
0 20000...

output:

result:

ok 200000 numbers

Test #39:

score: 15

Accepted

time: 196ms

memory: 22412kb

input:

200000 200000
200 200000
418 200000
690 200000
193 200000
63 200000
799 200000
474 200000
40 200000
287 200000
38 200000
204 200000
334 200000
258 200000
262 200000
269 200000
368 200000
167 200000
30 200000
51 200000
55 200000
119 200000
523 200000
33 200000
896 200000
253 200000
674 200000
119 200...

output:

result:

ok 200000 numbers

Test #40:

score: 15

Accepted

time: 186ms

memory: 19432kb

input:

200000 200000
611 200000
1167 200000
3159 200000
3415 200000
2254 200000
697 200000
6942 200000
23 200000
1856 200000
894 200000
6650 200000
3813 200000
5825 200000
5844 200000
5534 200000
6993 200000
3021 200000
515 200000
1584 200000
2031 200000
265 200000
8912 200000
6889 200000
6934 200000
833 2...

output:

result:

ok 200000 numbers

Test #41:

score: 15

Accepted

time: 168ms

memory: 20760kb

input:

200000 200000
3480 200000
36579 200000
10485 200000
18356 200000
20788 200000
3352 200000
4565 200000
33362 200000
6894 200000
25647 200000
5915 200000
19265 200000
3530 200000
26535 200000
18506 200000
18191 200000
35793 200000
7442 200000
993 200000
14550 200000
13606 200000
5553 200000
12284 2000...

output:

result:

ok 200000 numbers

Subtask #5:

score: 15

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #42:

score: 15

Accepted

time: 202ms

memory: 22736kb

input:

200000 200000
3 6
3 3
6 10
1 7
2 7
6 9
4 6
3 4
0 8
0 6
3 5
3 4
1 8
7 8
4 5
0 3
1 5
2 9
1 2
1 2
3 4
5 7
6 10
3 9
4 7
1 6
2 6
1 7
2 5
1 7
6 8
1 1
0 7
7 8
0 9
1 7
3 8
3 7
1 2
4 8
5 6
0 6
5 6
2 7
2 6
0 6
0 6
1 7
2 5
0 3
0 3
7 10
3 8
0 2
3 4
3 7
4 9
0 6
4 7
2 6
8 10
2 10
4 10
3 3
2 6
4 5
3 9
1 8
1 2
2 9
...

output:

result:

ok 200000 numbers

Test #43:

score: 15

Accepted

time: 199ms

memory: 24708kb

input:

200000 200000
5 45
27 99
7 23
51 88
16 62
10 24
16 80
43 70
12 45
35 55
6 99
77 91
40 82
66 99
30 47
18 80
9 36
4 12
26 51
37 64
39 52
2 11
2 69
57 81
15 98
8 36
19 27
32 34
35 97
22 23
15 89
53 77
2 89
25 55
25 90
4 91
13 77
37 65
67 89
8 52
20 58
10 18
31 81
35 59
41 56
71 74
18 61
56 77
51 74
40 ...

output:

result:

ok 200000 numbers

Test #44:

score: 15

Accepted

time: 212ms

memory: 25028kb

input:

200000 200000
193 894
142 229
346 553
197 496
389 718
370 600
650 853
476 695
764 767
220 571
238 714
516 700
137 692
1 293
835 962
34 536
208 482
148 225
377 804
75 864
277 925
278 864
296 647
390 757
179 283
338 602
571 746
447 852
315 365
7 390
634 689
76 239
16 60
244 388
385 822
451 836
301 373...

output:

result:

ok 200000 numbers

Test #45:

score: 15

Accepted

time: 230ms

memory: 21168kb

input:

200000 200000
3145 7698
6037 6154
6483 6707
6834 7442
7373 9621
5166 8045
7346 8938
2235 5518
2240 4134
586 3188
3845 8054
1258 5380
2409 2631
3360 5706
19 2771
1925 9642
6687 8264
4305 8055
2844 5474
2282 7810
1738 4706
1462 7466
17 6282
2481 6022
2363 2987
3633 4157
1460 2634
4866 8159
3154 5079
2...

output:

result:

ok 200000 numbers

Test #46:

score: 15

Accepted

time: 210ms

memory: 18300kb

input:

200000 200000
15540 44932
12196 33126
776 23774
35673 42863
31231 44618
16521 19781
8467 9747
5319 42216
13940 21955
3389 6981
22 11576
15248 17307
5734 35942
12762 45217
30349 47977
8869 11242
11199 25942
3415 10196
20104 40771
8813 28517
29726 34188
13420 13731
17526 30474
1033 44930
3143 10541
46...

output:

result:

ok 200000 numbers

Subtask #6:

score: 30

Accepted

Dependency #5:

100%

Accepted

Test #47:

score: 30

Accepted

time: 1077ms

memory: 56728kb

input:

1000000 1000000
4 5
2 9
6 8
3 10
2 7
4 7
0 8
2 3
0 5
2 8
2 8
0 1
0 3
1 5
1 4
1 2
2 3
0 10
1 10
2 9
5 9
5 10
2 7
0 10
2 6
3 6
2 6
1 5
3 10
3 6
1 3
2 9
3 4
0 0
1 1
4 5
2 9
6 6
1 1
1 4
0 1
0 0
4 6
0 3
2 4
3 3
0 1
2 6
5 10
2 10
2 4
1 2
2 5
4 9
3 6
4 6
0 8
2 2
1 2
0 3
8 10
1 3
3 5
2 6
2 3
1 1
6 10
4 10
0...

output:

result:

ok 1000000 numbers

Test #48:

score: 30

Accepted

time: 1095ms

memory: 57728kb

input:

1000000 1000000
16 22
5 42
3 33
32 43
44 79
1 74
17 91
8 52
25 89
12 39
61 79
26 40
4 91
47 54
2 74
4 65
60 80
49 76
3 72
15 92
26 81
12 81
18 42
30 60
11 36
62 100
46 83
4 9
1 68
18 64
28 35
52 64
2 36
51 78
32 53
13 76
33 80
18 31
20 63
31 72
55 65
29 90
4 69
5 62
2 58
6 58
15 81
17 18
72 98
0 9
1...

output:

result:

ok 1000000 numbers

Test #49:

score: 30

Accepted

time: 1129ms

memory: 59148kb

input:

1000000 1000000
729 973
98 551
14 904
352 402
692 789
72 618
4 983
242 715
459 667
179 390
65 391
57 539
107 847
413 548
250 490
224 690
250 700
118 884
136 616
470 830
92 769
286 394
181 740
20 23
163 665
657 767
100 280
661 883
135 258
36 128
28 401
51 247
86 524
73 738
11 869
659 917
49 562
140 9...

output:

result:

ok 1000000 numbers

Test #50:

score: 30

Accepted

time: 1241ms

memory: 55428kb

input:

1000000 1000000
271 7861
4188 5424
995 2871
2327 6988
253 7765
541 6033
6666 7294
5399 5653
117 5385
18 3452
7109 7699
2591 3833
1181 5927
1370 9294
5441 6215
5803 5944
1403 5911
2779 8613
2631 9816
1368 4502
3384 6549
4016 9290
4011 6899
8439 8620
2452 3500
2125 9610
5974 6101
1957 7445
1809 8994
1...

output:

result:

ok 1000000 numbers

Test #51:

score: 30

Accepted

time: 976ms

memory: 47712kb

input:

1000000 1000000
5477 25427
15832 45867
21319 40242
24542 38255
9564 34333
7226 18381
17794 27673
27818 38947
15867 35337
32893 41182
9109 21997
17274 18895
6956 28433
10294 49466
30828 49732
1120 12458
15518 26876
4777 39305
24706 46246
6175 17857
1022 41482
13809 22564
18376 40866
12659 20958
6644 ...

output:

result:

ok 1000000 numbers

Test #52:

score: 30

Accepted

time: 1205ms

memory: 55624kb

input:

1000000 1000000
12518 98574
6118 43962
1039 23278
10772 55452
12639 80876
775 73677
22168 55193
53756 77563
9159 82322
26293 62512
1288 80570
18004 41192
27725 38349
22931 66339
28914 34706
20429 59032
22939 31970
30894 46893
17769 20465
3053 91272
28608 82560
24975 73826
26131 28301
72980 75860
499...

output:

result:

ok 1000000 numbers

Test #53:

score: 30

Accepted

time: 883ms

memory: 45408kb

input:

1000000 1000000
37535 68329
34044 90924
66745 107225
81656 101462
1087 42107
27508 99984
3937 63277
38815 93956
31590 66983
79748 111265
95966 158488
5369 157882
58612 131865
69465 132812
20660 152657
31248 64679
12898 50107
6967 129782
33090 76511
39023 130707
62943 78076
3033 18966
36188 84046
292...

output:

result:

ok 1000000 numbers

Test #54:

score: 30

Accepted

time: 1066ms

memory: 47640kb

input:

1000000 1000000
15074 492048
25727 34552
92088 168699
269540 306007
219 202625
54535 241986
64045 380619
53606 268860
258737 310279
19044 456930
54322 73013
161501 289143
155226 241807
51093 60556
368921 385136
18370 452957
21905 96081
40985 155551
37188 251004
161885 265243
38134 391304
155105 3391...

output:

result:

ok 1000000 numbers

Test #55:

score: 30

Accepted

time: 867ms

memory: 37664kb

input:

1000000 1000000
225615 645997
165669 324384
488080 530722
65826 293286
242278 447838
683484 811652
223115 287602
113125 645440
48622 413280
130555 334599
102200 315597
54735 505596
99783 536797
245479 904353
46183 310819
168806 743603
509983 589593
325135 444502
211553 449082
393804 877074
211732 44...

output:

result:

ok 1000000 numbers

Test #56:

score: 30

Accepted

time: 944ms

memory: 45504kb

input:

1000000 1000000
12518 98574
6118 43962
1039 23278
10772 55452
12639 80876
775 73677
22168 55193
53756 77563
9159 82322
26293 62512
1288 80570
18004 41192
27725 38349
22931 66339
28914 34706
20429 59032
22939 31970
30894 46893
17769 20465
3053 91272
28608 82560
24975 73826
26131 28301
72980 75860
499...

output:

result:

ok 1000000 numbers