QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#507698#8672. 排队zhenghanyun0 104ms59192kbC++142.0kb2024-08-06 20:18:352024-08-06 20:18:35

Judging History

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

  • [2024-08-06 20:18:35]
  • 评测
  • 测评结果:0
  • 用时:104ms
  • 内存:59192kb
  • [2024-08-06 20:18:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 5;

int n, q, l[N], r[N], L[N], R[N], ans[N];

vector <int> vec[N];

int minx[N << 2], maxx[N << 2], tag[N << 2];

inline void push_up(int i) {
	minx[i] = min(minx[i << 1], minx[i << 1 | 1]);
	maxx[i] = min(maxx[i << 1], maxx[i << 1 | 1]);
}

inline void push_down(int i) {
	if (!tag[i]) {
		return;
	}
	minx[i << 1] += tag[i], minx[i << 1 | 1] += tag[i];
	maxx[i << 1] += tag[i], maxx[i << 1 | 1] += tag[i];
	tag[i << 1] += tag[i], tag[i << 1 | 1] += tag[i];
	tag[i] = 0;
}

inline void update(int ql, int qr, int i) {
	if (ql <= minx[i] && maxx[i] <= qr) {
		++minx[i], ++maxx[i], ++tag[i];
		return;
	}
	push_down(i);
	int mid1 = minx[i << 1], mid2 = maxx[i << 1 | 1];
	if (qr >= mid1) {
		update(ql, qr, i << 1);
	}
	if (ql <= mid2) {
		update(ql, qr, i << 1 | 1);
	}
	push_up(i);
}

inline void modify(int pos, int i, int l, int r) {
	if (l == r) {
		minx[i] = maxx[i] = 0;
		return;
	}
	push_down(i);
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		modify(pos, i << 1, l, mid);
	} else {
		modify(pos, i << 1 | 1, mid + 1, r);
	}
	push_up(i);
}

inline int query(int pos, int i, int l, int r) {
	if (l == r) {
		return minx[i];
	}
	push_down(i);
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		return query(pos, i << 1, l, mid);
	}
	return query(pos, i << 1 | 1, mid + 1, r);
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> l[i] >> r[i];
	}
	for (int i = 1; i <= q; ++i) {
		cin >> L[i] >> R[i];
		vec[R[i]].emplace_back(i);
	}
	for (int i = 1; i <= n; ++i) {
		modify(i, 1, 1, n);
		update(l[i], r[i], 1);
		for (auto id: vec[i]) {
			ans[id] = query(L[id], 1, 1, n);
		}
	}
	for (int i = 1; i <= q; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 10
Accepted
time: 3ms
memory: 40512kb

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
Runtime Error

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:


result:


Subtask #2:

score: 0
Runtime Error

Test #12:

score: 0
Runtime Error

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:


Subtask #3:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 102ms
memory: 56252kb

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:

28632
58948
22380
88063
23300
7497
39531
139737
4177
116908
95916
83101
3818
22790
37204
86261
53734
76846
101325
67388
41501
37224
81856
40379
109594
11255
5842
62394
101669
156656
65454
5655
19479
47445
25785
127928
24983
42909
95902
84539
35663
71532
34115
129089
56263
67026
133073
54285
23748
50...

result:

wrong answer 1st numbers differ - expected: '19141', found: '28632'

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 104ms
memory: 59192kb

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%