QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111780 | #6334. Passport | Scintilla | 6 | 347ms | 11416kb | C++14 | 3.0kb | 2023-06-08 18:55:53 | 2023-06-08 18:55:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
void cmax(int &a, int b) { a < b ? a = b : 1; }
void cmin(int &a, int b) { a > b ? a = b : 1; }
int n, L[N], R[N], id[N], fl[N], fr[N], f[N];
// int c[N];
// void build() { fill(c, c + N, inf); }
// void modify(int u, int k) { for (; u < N; u += u & -u) cmin(c[u], k); }
// int query(int u) { int res = inf; for (; u; u -= u & -u) cmin(res, c[u]); return res; }
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)
int dat[N << 2];
void maintain(int u) {
dat[u] = min(dat[ls], dat[rs]);
}
void build(int u = 1, int l = 1, int r = n) {
if (l == r) return dat[u] = inf, void();
build(ls, l, mid), build(rs, mid + 1, r);
maintain(u);
}
void modify(int p, int k, int u = 1, int l = 1, int r = n) {
if (l == r) return dat[u] = k, void();
if (p <= mid) modify(p, k, ls, l, mid);
else modify(p, k, rs, mid + 1, r);
maintain(u);
}
int query(int ql, int qr, int u = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return dat[u];
int res = inf;
if (ql <= mid) cmin(res, query(ql, qr, ls, l, mid));
if (qr > mid) cmin(res, query(ql, qr, rs, mid + 1, r));
return res;
}
#undef ls
#undef rs
#undef mid
int main() {
n = read();
rep(i, 1, n) L[i] = read(), R[i] = read(), id[i] = i;
sort(id + 1, id + n + 1, [&](int i, int j) {
return L[i] == L[j] ? R[i] > R[j] : L[i] < L[j];
});
fill(fl + 1, fl + n + 1, inf);
build();
rep(_i, 1, n) {
int i = id[_i];
fl[i] = L[i] == 1 ? 1 : query(L[i], R[i]) + 1;
modify(i, fl[i]);
}
sort(id + 1, id + n + 1, [&](int i, int j) {
return R[i] == R[j] ? L[i] < L[j] : R[i] > R[j];
});
fill(fr + 1, fr + n + 1, inf);
build();
rep(_i, 1, n) {
int i = id[_i];
fr[i] = R[i] == n ? 1 : query(L[i], R[i]) + 1;
modify(i, fr[i]);
}
rep(i, 1, n) f[i] = fl[i] + fr[i] - 1;
sort(id + 1, id + n + 1, [&](int i, int j) {
return L[i] == L[j] ? R[i] > R[j] : L[i] < L[j];
});
build();
rep(_i, 1, n) {
int i = id[_i];
cmin(f[i], query(L[i], R[i]) + 1);
modify(i, f[i]);
}
sort(id + 1, id + n + 1, [&](int i, int j) {
return R[i] == R[j] ? L[i] < L[j] : R[i] > R[j];
});
build();
rep(_i, 1, n) {
int i = id[_i];
cmin(f[i], query(L[i], R[i]) + 1);
modify(i, f[i]);
}
for (int q = read(); q; -- q) {
int x = read();
printf("%d\n", f[x] <= n ? f[x] : -1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 7672kb
input:
2 1 1 1 2 1 1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7600kb
input:
2 1 2 2 2 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 347ms
memory: 11248kb
input:
196001 1 408 2 37822 1 1221 1 160899 4 62751 3 21706 2 4118 8 70696 8 4916 3 24286 9 443 8 171744 11 170980 7 3541 12 16428 8 71164 1 186827 11 234 2 23141 4 17143 21 9522 10 24 19 15936 3 15884 17 426 14 3188 17 168317 4 1560 25 35 16 39439 21 122 4 17507 8 97645 11 824 25 59856 30 9265 7 151420 37...
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 167ms
memory: 11356kb
input:
198001 1 17 1 19 1 4 2 20 3 15 6 10 1 20 3 9 3 9 10 19 6 27 8 29 12 24 3 23 8 23 16 19 11 23 1 19 13 30 19 32 4 28 15 33 23 33 8 36 16 30 23 40 11 42 27 34 20 30 21 36 31 39 30 35 32 33 29 48 27 43 33 41 25 53 28 51 29 56 37 55 35 54 36 52 35 44 31 58 36 54 42 56 47 49 41 59 37 64 44 50 34 55 41 56 ...
output:
15219
result:
ok single line: '15219'
Test #5:
score: 0
Accepted
time: 127ms
memory: 11416kb
input:
200000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53...
output:
199999
result:
ok single line: '199999'
Test #6:
score: 0
Accepted
time: 75ms
memory: 11180kb
input:
195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195...
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 87ms
memory: 11092kb
input:
156789 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 783...
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 16
Accepted
time: 1ms
memory: 9708kb
input:
2 1 1 1 2 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 3ms
memory: 7708kb
input:
2 1 2 2 2 1 2
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 3ms
memory: 7540kb
input:
6 1 1 2 2 1 3 3 5 5 6 1 6 1 4
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 3ms
memory: 7664kb
input:
9 1 1 2 2 3 3 1 4 2 8 5 7 4 9 8 8 9 9 1 6
output:
3
result:
ok single line: '3'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7596kb
input:
9 1 1 2 2 3 3 1 4 2 8 4 9 5 7 8 8 9 9 1 7
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 3ms
memory: 7720kb
input:
10 1 1 2 2 3 3 2 10 1 6 3 8 1 8 6 8 3 9 10 10 1 4
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 0ms
memory: 7564kb
input:
285 1 13 1 16 3 16 3 25 3 94 5 100 2 92 7 10 9 10 1 270 11 11 9 93 5 43 4 115 11 15 10 66 16 20 16 58 16 22 3 124 15 31 1 59 23 23 24 24 19 28 22 126 27 27 20 89 16 218 24 42 10 135 21 156 8 187 27 265 34 35 34 41 15 233 33 107 38 44 5 284 41 42 13 169 33 51 5 81 41 89 44 52 43 50 23 86 42 62 4 95 4...
output:
4
result:
ok single line: '4'
Test #15:
score: 0
Accepted
time: 3ms
memory: 9712kb
input:
296 1 1 1 7 2 6 2 12 4 5 5 8 1 13 6 13 5 17 2 13 3 13 11 17 13 20 10 21 9 16 11 22 12 19 14 19 14 19 12 28 14 23 20 25 15 23 18 31 20 32 20 26 21 33 24 32 22 37 29 35 29 36 31 38 25 34 32 35 34 39 36 37 29 42 36 46 39 43 40 44 33 46 41 48 43 51 39 45 44 47 43 50 41 53 44 52 43 52 45 51 47 58 48 59 5...
output:
49
result:
ok single line: '49'
Test #16:
score: -16
Wrong Answer
time: 1ms
memory: 7572kb
input:
300 1 300 1 300 1 300 2 300 1 299 4 299 5 296 6 298 7 294 7 295 9 292 9 291 11 290 12 291 12 292 13 287 14 286 16 285 17 284 18 284 19 282 20 281 21 281 21 280 21 278 24 277 24 276 26 275 27 274 27 273 29 287 30 271 28 273 27 269 33 268 34 268 31 284 30 265 37 265 38 264 38 264 40 261 40 260 40 260 ...
output:
11
result:
wrong answer 1st lines differ - expected: '10', found: '11'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 24
Accepted
time: 6ms
memory: 9744kb
input:
2337 1 3 2 77 1 1397 2 222 3 62 6 1896 7 10 6 950 9 9 10 16 11 455 9 588 13 16 7 1245 9 1342 8 1727 7 122 11 653 9 1094 2 57 11 81 19 1290 6 1584 16 79 14 215 21 61 27 27 16 1458 16 198 26 180 31 31 11 240 33 36 11 121 34 1542 9 1752 14 456 36 43 36 2244 40 40 4 517 42 662 31 1350 33 162 30 843 28 1...
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 4ms
memory: 7568kb
input:
2486 1 12 2 8 1 7 3 12 2 11 3 15 1 8 4 11 9 15 3 21 11 13 4 15 9 21 9 19 5 15 8 20 8 25 16 24 11 29 11 23 18 23 14 32 17 24 13 27 15 30 21 34 16 29 20 35 19 32 29 34 20 39 21 43 29 40 28 43 26 44 31 45 28 43 35 38 30 40 37 46 40 43 42 42 42 45 43 54 39 51 40 51 45 54 46 57 39 53 47 53 47 54 41 59 49...
output:
314
result:
ok single line: '314'
Test #21:
score: -24
Wrong Answer
time: 2ms
memory: 7588kb
input:
2500 1 2500 1 2500 1 2500 2 2500 2 2499 3 2498 5 2496 6 2495 7 2495 8 2493 8 2492 6 2492 11 2491 12 2489 12 2490 12 2491 15 2486 15 2485 17 2484 18 2483 15 2482 20 2483 21 2481 19 2479 23 2481 23 2477 21 2477 25 2476 27 2474 28 2473 29 2472 30 2475 31 2470 30 2469 33 2468 32 2467 33 2466 33 2466 33 ...
output:
61
result:
wrong answer 1st lines differ - expected: '60', found: '61'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 8
Accepted
time: 2ms
memory: 9680kb
input:
2419 1 883 1 29 3 41 4 2201 1 808 6 45 7 1456 6 134 6 1372 1 1776 4 441 7 208 5 28 4 604 7 56 9 617 8 2115 15 60 13 456 10 2071 18 23 18 39 5 39 21 35 4 75 25 44 24 640 21 30 4 860 30 31 18 78 32 779 1 927 33 34 19 59 34 181 21 502 23 155 39 39 2 254 30 641 42 50 10 2000 41 2220 18 632 35 48 27 905 ...
output:
3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 4 4 3 4 4 3 4 3 4 4 4 3 5 4 4 3 4 4 4 4 4 -1 3 4 4 3 3 4 4 4 3 3 4 4 3 -1 3 4 4 4 3 -1 4 4 4 3 4 4 4 4 4 4 3 3 4 5 4 3 3 4 4 3 4 4 3 4 3 4 4 -1 -1 3 4 4 3 4 4 3 4 3 4 5 4 4 4 4 3 4 4 4 3 4 5 4 4 4 4 4 3 4 4 4 4 4 4 4 3 4 4 4 -1 4 3 3 3 4 4 4 5 4 4 3 4 4 5 -1 4 4 4 4...
result:
ok 2419 lines
Test #29:
score: 0
Accepted
time: 5ms
memory: 7620kb
input:
2500 1 7 1 6 1 8 1 15 5 14 2 17 5 18 8 17 2 13 3 12 3 14 12 22 4 15 6 18 14 16 8 20 6 22 10 22 12 28 11 28 20 24 12 33 16 29 23 28 20 28 19 35 18 30 24 39 20 33 19 33 30 40 23 32 26 37 28 36 30 45 35 40 36 41 34 44 34 46 29 44 37 50 33 44 39 49 35 54 40 54 39 46 36 50 47 54 44 49 46 61 42 58 41 58 4...
output:
314 314 314 313 315 314 315 315 314 314 314 314 314 315 315 314 314 314 313 313 314 313 314 314 314 313 314 314 314 314 314 314 314 314 313 314 314 314 314 313 313 314 314 313 313 314 313 314 314 313 313 313 314 313 313 314 314 314 314 313 313 313 314 314 314 314 314 314 313 314 314 313 314 314 313 ...
result:
ok 2500 lines
Test #30:
score: 0
Accepted
time: 0ms
memory: 9624kb
input:
2500 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 5...
output:
2499 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 2498 ...
result:
ok 2500 lines
Test #31:
score: -8
Wrong Answer
time: 5ms
memory: 7724kb
input:
2500 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 634th lines differ - expected: '1263', found: '-1'
Subtask #5:
score: 0
Wrong Answer
Test #33:
score: 46
Accepted
time: 345ms
memory: 11252kb
input:
196830 1 67357 2 183304 3 23390 4 54 1 145887 3 27807 3 12376 1 1013 3 113274 3 191874 6 23342 9 2113 13 94245 3 141449 10 1727 3 51 17 99028 6 193803 8 7452 6 121537 9 23658 18 611 6 4756 4 5141 8 8547 8 66922 13 7021 9 72 3 53043 16 167381 2 15530 5 192 33 33 9 92655 10 36182 20 19992 36 24454 1 6...
output:
3 3 3 4 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 4 -1 3 3 3 3 3 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 3 3 4 3 4 3 3 3 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 3 3 3 3 3 4 3 3 3 3 3 3 3 3 4 3 3 -1 3 3 3 3 3 3 3 3 3 4 3 3 3 3 3 3 4 -1 3 4 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
result:
ok 196830 lines
Test #34:
score: 0
Accepted
time: 185ms
memory: 11376kb
input:
199765 1 6 1 12 3 15 1 12 4 7 5 14 5 16 1 25 9 12 7 11 9 25 9 15 2 22 12 28 9 29 16 21 11 26 12 31 12 24 11 28 19 35 21 26 6 35 7 39 11 35 10 35 20 27 23 31 27 34 13 47 21 42 27 41 19 45 33 37 24 42 29 40 36 51 38 47 35 47 39 46 41 55 42 54 26 56 36 46 35 55 40 57 31 50 35 64 42 65 39 61 39 54 40 69...
output:
15336 15335 15335 15335 15336 15335 15335 15334 15336 15335 15335 15336 15335 15335 15335 15336 15335 15335 15335 15335 15335 15335 15335 15334 15335 15335 15335 15335 15336 15335 15335 15336 15335 15336 15335 15336 15336 15336 15336 15336 15336 15336 15335 15336 15335 15336 15335 15335 15335 15336 ...
result:
ok 199765 lines
Test #35:
score: -46
Wrong Answer
time: 223ms
memory: 11248kb
input:
199851 1 199851 1 199851 1 199851 1 199850 3 199849 4 199848 5 199849 6 199850 7 199845 8 199845 9 199844 9 199842 10 199842 12 199840 13 199839 14 199838 14 199837 16 199838 16 199836 18 199836 19 199833 20 199833 21 199831 10 199830 22 199829 24 199832 16 199828 26 199828 27 199826 27 199826 29 19...
output:
1 1 1 2 2 3 2 2 3 3 3 3 3 4 4 4 5 4 5 5 5 5 5 4 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 7 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 9 9 10 10 10 9 10 10 10 11 10 11 11 11 11 11 10 11 11 12 12 12 12 12 12 12 12 12 12 13 13 13 14 14 14 14 14 13 1...
result:
wrong answer 470th lines differ - expected: '33', found: '34'