QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #508255 | #8672. 排队 | zhenghanyun | 0 | 81ms | 48220kb | C++14 | 1.7kb | 2024-08-07 11:45:05 | 2024-08-07 11:45:06 |
Judging History
answer
// test
#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 maxr, int i, int l, int r) {
if (ql <= minx[i] && maxx[i] <= qr && r <= maxr) {
++minx[i], ++maxx[i], ++tag[i];
return;
}
push_down(i);
int mid1 = minx[i << 1], mid2 = maxx[i << 1 | 1], mid = (l + r) >> 1;
if (qr >= mid1) {
update(ql, qr, maxr, i << 1, l, mid);
}
if (ql <= mid2 && maxr > mid) {
update(ql, qr, maxr, 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() {
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) {
update(l[i], r[i], i, 1, 1, n);
// 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
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 38464kb
input:
3 3 0 0 1 2 0 2 1 1 1 3 2 3
output:
0 0 0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'
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: 79ms
memory: 46104kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
wrong answer 1st numbers differ - expected: '19141', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 81ms
memory: 48220kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
wrong answer 1st numbers differ - expected: '71224', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%