QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589974#8672. 排队cancan12345615 238ms55612kbC++142.4kb2024-09-25 20:52:432024-09-25 20:52:48

Judging History

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

  • [2024-09-25 20:52:48]
  • 评测
  • 测评结果：15
  • 用时：238ms
  • 内存：55612kb
查看
  • [2024-09-25 20:52:43]
  • 提交

answer

#include <cstdio>
#include <vector>
using namespace std;
const int N = 1000005;
vector < pair < int, int > > vec[N];
struct Node {
	int l, r, mn, mx, add;
} node[4 * N];
void push_up(int p) {
	node[p].mn = min(node[2 * p].mn, node[2 * p + 1].mn);
	node[p].mx = min(node[2 * p].mx, node[2 * p + 1].mx);
}
void push_tag(int p, int tag) {
	node[p].mn += tag;
	node[p].mx += tag;
	node[p].add += tag;
}
void push_down(int p) {
	push_tag(2 * p, node[p].add);
	push_tag(2 * p + 1, node[p].add);
	node[p].add = 0;
}
void build(int p, int l, int r) {
	node[p].l = l;
	node[p].r = r;
	node[p].mn = node[p].mx = node[p].add = 0;
	if (l != r) {
		int mid = (l + r) / 2;
		build(2 * p, l, mid);
		build(2 * p + 1, mid + 1, r);
	}
}
int query_left(int p, int x) {
	// first <= x
	if (node[p].l == node[p].r) {
		return node[p].l;
	} else {
		push_down(p);
		if (node[2 * p].mn <= x) {
			return query_left(2 * p, x);
		} else {
			return query_left(2 * p + 1, x);
		}
	}
}
int query_right(int p, int x) {
	// last >= x
	if (node[p].l == node[p].r) {
		return node[p].l;
	} else {
		push_down(p);
		if (node[2 * p + 1].mx >= x) {
			return query_right(2 * p + 1, x);
		} else {
			return query_right(2 * p, x);
		}
	}
}
int query(int p, int x) {
	if (node[p].l == node[p].r) {
		return node[p].mn;
	} else {
		push_down(p);
		int mid = (node[p].l + node[p].r) / 2;
		if (x <= mid) {
			return query(2 * p, x);
		} else {
			return query(2 * p + 1, x);
		}
	}
}
void add(int p, int l, int r) {
	if (l <= node[p].l && node[p].r <= r) {
		push_tag(p, 1);
	} else {
		push_down(p);
		int mid = (node[p].l + node[p].r) / 2;
		if (l <= mid) {
			add(2 * p, l, r);
		}
		if (mid + 1 <= r) {
			add(2 * p + 1, l, r);
		}
		push_up(p);
	}
}
int L[N], R[N], ans[N];
int main() {
//	freopen("in.txt", "r", stdin);
	int n, q;
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &L[i], &R[i]);
	}
	for (int l, r, i = 1; i <= q; i++) {
		scanf("%d %d", &l, &r);
		vec[r].push_back(make_pair(l, i));
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		int l = query_left(1, R[i]);
		int r = query_right(1, L[i]);
		r = min(r, i);
		if (l <= r) {
			add(1, l, r);
		}
		for (pair < int, int > p : vec[i]) {
			ans[p.second] = query(1, p.first);
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}
源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 4ms
memory: 34676kb

input:

3 3
0 0
1 2
0 2
1 1
1 3
2 3

output:

1
3
1

result:

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

Test #2:

score: 0
Wrong Answer
time: 3ms
memory: 33976kb

input:

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

output:

11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
10
11
11
11
11
9
8
11
11
11
11
11
11
11
11
7
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
10
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
9
11
11
1...

result:

wrong answer 22nd numbers differ - expected: '11', found: '10'

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 150ms
memory: 50820kb

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:

11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
...

result:

wrong answer 1957th numbers differ - expected: '1', found: '8'

Subtask #3:

score: 15
Accepted

Test #22:

score: 15
Accepted
time: 196ms
memory: 55612kb

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:

19141
39288
14841
58655
15427
4999
26338
93250
2826
78084
64070
55481
2565
15173
24866
57627
35887
51335
67552
44939
27730
24781
54502
26903
73199
7553
3836
41740
67889
104576
43522
3766
13007
31659
17264
85349
16595
28681
64012
56457
23856
47820
22752
86123
37679
44828
88810
36305
15843
33728
10005...

result:

ok 200000 numbers

Test #23:

score: 15
Accepted
time: 187ms
memory: 48888kb

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:

168949
95410
33682
47935
82249
25613
65578
22342
60917
30684
99457
21252
87719
9508
41909
17405
96346
6219
110867
56725
71026
2090
45186
37640
26229
36720
91410
64919
7095
29903
44679
40307
100104
41603
87434
53924
53758
80720
59404
164539
38810
117092
13565
110110
38606
32273
93240
81294
10356
1504...

result:

ok 200000 numbers

Test #24:

score: 15
Accepted
time: 190ms
memory: 48844kb

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:

69217
146306
97579
32894
129999
10418
98425
25273
33368
29464
14306
2073
112582
140228
24801
40781
52137
17338
110491
48418
54730
20451
84100
80588
2089
108163
29975
56448
14978
35560
102453
18613
30516
18699
83182
28795
25862
126187
116576
99593
36207
13935
27150
75205
66741
91089
151786
19917
2529...

result:

ok 200000 numbers

Test #25:

score: 15
Accepted
time: 201ms
memory: 49256kb

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:

101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
101
...

result:

ok 200000 numbers

Test #26:

score: 15
Accepted
time: 200ms
memory: 55540kb

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:

1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
986
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
834
1001
999
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
995
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001
1001...

result:

ok 200000 numbers

Test #27:

score: 15
Accepted
time: 238ms
memory: 48888kb

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:

9992
10001
10001
10000
10001
10001
9910
9932
2155
6995
10001
9347
10001
10001
10000
8952
9997
10000
9996
9999
10001
9996
10001
10000
9949
8842
9944
10000
10000
6517
9719
7997
10001
9875
10000
10001
10001
10001
10001
7481
10001
564
9962
8180
10001
7708
9902
9995
6677
10000
10000
9993
9841
6942
9584
1...

result:

ok 200000 numbers

Test #28:

score: 15
Accepted
time: 238ms
memory: 48676kb

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:

48090
32992
22437
48207
21332
45359
39653
11005
43989
17371
8176
34898
30342
43305
36171
34310
36953
26580
26406
40517
30042
24009
21601
48636
34590
44645
6569
1680
36941
44685
8184
29538
47471
13134
37634
44021
16542
45480
34004
2798
44629
42393
43534
32749
42758
39005
46942
906
35042
32188
39406
4...

result:

ok 200000 numbers

Test #29:

score: 15
Accepted
time: 224ms
memory: 48596kb

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:

20413
33643
27062
9573
23562
70288
46728
62984
61505
69707
52256
43819
42924
84768
46751
32254
29961
25002
61760
47063
54538
23381
4229
40146
56797
35682
73141
55198
81237
4145
14779
79432
46593
8554
55961
48948
59145
73439
77423
43568
51349
68840
23328
1413
10825
33789
61183
12488
53414
60374
77583...

result:

ok 200000 numbers

Test #30:

score: 15
Accepted
time: 187ms
memory: 48840kb

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:

51
51
51
51
51
51
51
51
51
27
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
51
...

result:

ok 200000 numbers

Test #31:

score: 15
Accepted
time: 187ms
memory: 51384kb

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:

11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
...

result:

ok 200000 numbers

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 181ms
memory: 51432kb

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:

64014
11841
56457
26035
47022
28565
145529
132058
161885
77064
23758
109501
97006
9544
81743
17684
48544
8530
846
87798
71418
55405
9237
2650
21133
25541
123535
77168
663
14467
3632
172197
55633
62119
8574
102598
121527
8528
23030
16928
13372
9567
6026
111201
12376
20708
81746
98573
124784
27712
688...

result:

wrong answer 1st numbers differ - expected: '71224', found: '64014'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-04 04:31:57 | 開源專案