QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #507698 | #8672. 排队 | zhenghanyun | 0 | 104ms | 59192kb | C++14 | 2.0kb | 2024-08-06 20:18:35 | 2024-08-06 20:18:35 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%