QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #508253 | #8672. 排队 | zhenghanyun | 0 | 134ms | 48212kb | C++14 | 1.7kb | 2024-08-07 11:42:47 | 2024-08-07 11:42:47 |
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 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
Runtime Error
Test #1:
score: 10
Accepted
time: 3ms
memory: 36476kb
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: 134ms
memory: 48212kb
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:
19143 39292 14844 58660 15429 5003 26340 93253 2826 78087 64072 55483 2567 15176 24869 57628 35889 51338 67555 44941 27733 24783 54507 26906 73202 7555 3837 41742 67890 104578 43526 3768 13007 31661 17267 85353 16597 28683 64013 56459 23857 47822 22754 86125 37682 44828 88812 36307 15844 33732 10005...
result:
wrong answer 1st numbers differ - expected: '19141', found: '19143'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 133ms
memory: 46140kb
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%