ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#477 | #94. 「NOIP2021」报数 | Pigsyy | 100 | 8001ms | 149072kb | C++23 | 4.4kb | 2025-04-24 20:54:42 | 2025-04-24 20:54:43 |
answer
#include <bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define pii pair<int,int>
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int N = 5e5;
struct Edge {
int nxt;
int to;
} ed[2 * N];
int head[N + 9];
int pp;
void adde(int x, int y) {
++pp;
ed[pp].nxt = head[x];
ed[pp].to = y;
head[x] = pp;
}
struct question {
int id, l, r, k;
} q[N + 9];
struct node {
int l, r, x;
} sk[N + 9];
int dep[N + 9];
int st[20][N + 9];
int dfn[N + 9];
int a[N + 9];
int n, dfntot;
void dfs(int x, int fa) {
dep[x] = dep[fa] + 1;
st[0][dfn[x] = ++dfntot] = dep[fa];
for (int i = head[x], u = ed[i].to; i; u = ed[i = ed[i].nxt].to)
if (u != fa)
dfs(u, x);
}
int ask(int x) {
int u = dfn[x], v = dfn[x + 1];
if (u > v)
swap(u, v);
int l = __lg(v - u++);
return min(st[l][u], st[l][v - (1 << l) + 1]);
}
void init() {
F(i, 1, __lg(n))F(j, 1, n - (1 << i) + 1) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
F(i, 1, n - 1) sk[i].x = a[i] = ask(i);
int stk[N + 9], top = 0;
stk[0] = 0;
F(i, 1, n - 1) {
while (top && a[stk[top]] >= a[i])
sk[stk[top--]].r = i - 1;
sk[i].l = stk[top] + 1;
stk[++top] = i;
}
F(i, 1, top) sk[stk[i]].r = n - 1;
}
void chkmin(int &x, int y) {
if (y < x)
x = y;
}
void chkmax(int &x, int y) {
if (y > x)
x = y;
}
namespace zkw {
int tr[1 << 21], n;
void init(int n_) {
n = 1;
while (n <= n_)
n <<= 1;
memset(tr, 0, sizeof(int) * (2 * n + 1));
}
void modify(int x, int y) {
if (tr[x += n] < y)
tr[x] = y;
else
return ;
for (; x >>= 1;)
tr[x] = max(tr[x << 1], tr[x << 1 | 1]);
}
int ask(int l, int r) {
int ans = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ans = max(ans, tr[l++]);
if (r & 1)
ans = max(ans, tr[--r]);
}
return ans;
}
}
int out[N + 9];
int m;
namespace solve {
int st[20][N + 9];
void main() {
F(i, 1, n) st[0][i] = dep[i];
F(i, 1, __lg(n))F(j, 1, n - (1 << i) + 1)st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
F(i, 1, m)if (q[i].k == 0) {
q[i].r++;
int l = __lg(q[i].r - q[i].l + 1);
out[i] = max(st[l][q[i].l], st[l][q[i].r - (1 << l) + 1]);
}
}
}
void read(int &x) {
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
}
char hi[10];
int hii;
void write(int x) {
hii = 0;
while (x)
hi[++hii] = x % 10, x /= 10;
G(i, hii, 1)putchar(hi[i] + '0');
}
int main() {
read(n);
F(i, 1, n - 1) {
int u, v;
read(u);
read(v);
adde(u, v);
adde(v, u);
}
dfs(1, 0);
read(m);
F(i, 1, m)q[i].id = i, read(q[i].l), read(q[i].r), read(q[i].k), q[i].k--, q[i].r--;
solve::main();
init();
sort(q + 1, q + m + 1, [](const question & a, const question & b) {
return a.k > b.k;
});
sort(sk + 1, sk + n, [](const node & a, const node & b) {
return a.r - a.l > b.r - b.l;
});
zkw::init(n);
int tot = 0;
F(i, 1, m) {
if (!q[i].k)
break;
while (tot < n && sk[tot + 1].r - sk[tot + 1].l + 1 >= q[i].k) {
++tot;
zkw::modify(sk[tot].l, sk[tot].x);
}
chkmax(out[q[i].id], zkw::ask(q[i].l, q[i].r - q[i].k + 1));
}
sort(q + 1, q + m + 1, [](const question & a, const question & b) {
return a.l < b.l;
});
sort(sk + 1, sk + n, [](const node & a, const node & b) {
return a.l < b.l;
});
zkw::init(n);
tot = 0;
F(i, 1, m) {
if (!q[i].k)
continue;
while (tot < n && sk[tot + 1].l <= q[i].l) {
++tot;
zkw::modify(sk[tot].r, sk[tot].x);
}
chkmax(out[q[i].id], zkw::ask(q[i].l + q[i].k - 1, n));
}
F(i, 1, m)write(out[i]), putchar('\n');
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 4
Accepted
time: 1ms
memory: 48428kb
input:
498 89 22 22 63 22 67 67 149 89 74 89 80 63 54 54 205 63 177 205 20 149 66 80 96 96 194 194 170 96 1...
output:
1 3 1 1 3 1 1 3 3 3 3 3 1 3 1 3 1 3 2 1 3 3 3 1 32 3 1 3 2 1 3 1 1 3 3 1 1 1 42 3 6 3 3 1 3 3 1 1 1 ...
result:
ok 500 tokens
Test #2:
score: 4
Accepted
time: 3ms
memory: 48508kb
input:
496 376 35 35 334 35 49 376 328 35 184 334 9 184 216 35 50 49 108 9 79 79 274 9 325 274 416 416 272 ...
output:
7 3 15 2 1 1 2 2 1 23 2 1 1 1 2 2 1 8 1 1 2 2 1 1 32 2 2 2 28 2 2 2 1 2 1 2 5 1 14 8 2 2 1 2 1 2 2 1...
result:
ok 500 tokens
Test #3:
score: 4
Accepted
time: 10ms
memory: 64888kb
input:
4996 58 212 212 251 251 501 251 358 58 483 501 200 212 173 501 21 501 34 34 506 483 266 173 144 266 ...
output:
414 358 358 5 219 472 358 219 55 5 5 358 17 5 358 358 219 5 358 1 358 72 151 1 219 358 1 1 1 358 305...
result:
ok 4995 tokens
Test #4:
score: 4
Accepted
time: 5ms
memory: 65144kb
input:
4997 599 56 599 83 56 283 56 292 283 764 283 148 56 770 83 251 83 362 362 199 770 871 362 448 871 48...
output:
427 2 426 200 348 1 447 89 151 34 89 89 340 208 1 340 1 387 257 1 2 1 414 2 2 340 2 2 456 2 2 387 2 ...
result:
ok 5000 tokens
Test #5:
score: 4
Accepted
time: 4ms
memory: 65028kb
input:
5000 130 241 241 561 561 17 130 208 130 444 208 437 208 362 437 325 325 419 325 47 325 629 362 487 6...
output:
406 392 70 151 49 495 518 4 3 3 5 384 159 384 518 4 406 4 384 3 4 4 4 384 406 518 384 392 4 166 4 40...
result:
ok 4999 tokens
Test #6:
score: 4
Accepted
time: 128ms
memory: 90500kb
input:
100000 1 89135 89135 42606 42606 51140 51140 88708 88708 24332 24332 42871 42871 42697 42697 49402 4...
output:
2309 2309 3412 332 7111 17 3172 3 5873 5303 2309 13804 8431 3 1429 7111 1475 1475 7081 21 2013 691 1...
result:
ok 99973 tokens
Test #7:
score: 4
Accepted
time: 94ms
memory: 92608kb
input:
100000 1 9530 9530 22076 22076 39846 39846 47126 47126 11168 11168 31227 31227 92667 92667 73020 730...
output:
3467 1382 1640 1689 1162 12809 32 1429 3624 3944 2807 1988 3944 1848 2030 662 1280 1280 6106 5885 94...
result:
ok 99955 tokens
Test #8:
score: 4
Accepted
time: 96ms
memory: 90292kb
input:
100000 1 56545 56545 4442 4442 30021 30021 12958 12958 3882 3882 81161 81161 17303 17303 59356 59356...
output:
6159 1771 6215 2229 1517 1342 2017 1629 1871 2 2369 14425 12052 10 1574 8556 5439 23559 6215 12052 2...
result:
ok 99911 tokens
Test #9:
score: 4
Accepted
time: 105ms
memory: 90548kb
input:
100000 1 28773 28773 60979 60979 62259 62259 23921 23921 94894 94894 14535 14535 25483 25483 15766 1...
output:
2311 1164 14 1414 1131 5143 2311 9483 2 2579 2311 959 1582 2311 1582 5143 13314 2510 3 2 1288 2745 4...
result:
ok 99997 tokens
Test #10:
score: 4
Accepted
time: 632ms
memory: 149072kb
input:
500000 1 266014 266014 196927 196927 19617 19617 450868 450868 244252 244252 69345 69345 240592 2405...
output:
13932 19218 14644 8231 25076 12046 12933 31734 31734 13042 136956 6484 6881 160193 7126 13681 35179 ...
result:
ok 499980 tokens
Test #11:
score: 4
Accepted
time: 610ms
memory: 148916kb
input:
500000 1 278484 278484 369808 369808 117284 117284 296213 296213 395873 395873 259275 259275 43124 4...
output:
18403 12923 25685 12923 19248 265 11987 14694 18604 9186 10151 11405 35602 4 6 40328 13688 7938 9381...
result:
ok 499988 tokens
Test #12:
score: 4
Accepted
time: 619ms
memory: 146160kb
input:
500000 1 402048 402048 181762 181762 153002 153002 57994 57994 330080 330080 309815 309815 101203 10...
output:
12167 12167 22077 94086 55431 10851 18966 19 12167 12448 12069 12167 86819 22077 17265 22690 86819 1...
result:
ok 499901 tokens
Test #13:
score: 4
Accepted
time: 597ms
memory: 145204kb
input:
500000 1 404040 404040 422879 422879 251314 251314 437072 437072 166277 166277 496632 496632 137251 ...
output:
53754 112704 4 118319 6457 14029 12855 77570 17671 17671 80826 33369 12855 17671 440 12855 10913 223...
result:
ok 499955 tokens
Test #14:
score: 4
Accepted
time: 545ms
memory: 115344kb
input:
500000 945 968 968 931 968 52 931 923 945 696 696 900 696 180 696 8 52 581 900 867 900 629 581 453 4...
output:
3848 2490 1128 79 699 79 1 946 4530 1 5995 5763 79 7092 1 1754 1157 6698 7032 4251 79 1 6265 1012 11...
result:
ok 499959 tokens
Test #15:
score: 4
Accepted
time: 542ms
memory: 114344kb
input:
500000 668 773 668 181 181 92 773 267 181 471 92 260 92 455 455 574 267 298 455 81 574 838 838 434 8...
output:
4 3181 303 1405 4 4 3127 4 1361 1 303 1489 1187 303 4 3711 987 4 4 4 4 303 1 303 2367 4 684 1302 4 2...
result:
ok 499973 tokens
Test #16:
score: 4
Accepted
time: 538ms
memory: 114924kb
input:
500000 146 93 146 98 146 171 93 12 146 52 52 237 12 279 279 36 171 189 52 243 237 122 122 25 122 212...
output:
329 3041 329 28 1247 177 712 8422 13 28 329 355 3601 3918 329 6801 3041 5194 712 329 3760 329 329 32...
result:
ok 499982 tokens
Test #17:
score: 4
Accepted
time: 99ms
memory: 88748kb
input:
100000 9 271 9 115 115 270 271 234 9 136 136 22 9 134 115 196 22 195 196 52 22 151 22 268 134 11 268...
output:
4848 4221 655 4754 2 4219 4447 1 2 4734 4219 4874 2 4846 3621 1 4846 4854 2 4447 2 4848 3989 2282 48...
result:
ok 99996 tokens
Test #18:
score: 4
Accepted
time: 112ms
memory: 84360kb
input:
100000 38 135 38 114 38 155 135 645 38 52 135 593 155 491 645 251 593 245 491 40 52 269 245 622 40 3...
output:
668 4630 197 668 2159 3213 4630 177 4630 148 4638 4637 197 4 197 4638 4304 24 4630 114 10 4602 114 4...
result:
ok 99972 tokens
Test #19:
score: 4
Accepted
time: 115ms
memory: 86680kb
input:
100000 255 350 255 14 14 222 14 415 222 40 415 232 14 65 40 174 222 438 65 29 232 152 232 261 261 20...
output:
3757 3942 96 3852 2350 1787 1 3852 3850 124 1 124 124 124 3483 3852 2656 3757 1685 3951 124 3942 124...
result:
ok 99925 tokens
Test #20:
score: 4
Accepted
time: 113ms
memory: 84312kb
input:
100000 880 278 278 659 278 211 659 509 659 270 659 634 659 819 819 501 659 474 474 11 474 221 270 69...
output:
1 4896 4892 1 4896 1 394 4892 4898 4896 1 4892 1 3017 4906 1 4926 4892 4896 1 4624 4901 4892 1 4892 ...
result:
ok 99938 tokens
Test #21:
score: 4
Accepted
time: 587ms
memory: 118240kb
input:
500000 9 278 278 66 9 410 278 580 580 5 5 609 410 610 410 44 609 632 44 304 5 210 632 692 610 529 63...
output:
3 7216 7216 7225 3 363 152 7216 7223 7223 2011 5122 3 7151 152 7223 7216 5250 3 7216 7225 3 7216 513...
result:
ok 499975 tokens
Test #22:
score: 4
Accepted
time: 620ms
memory: 114712kb
input:
500000 471 528 471 418 471 256 418 18 18 64 18 461 256 577 577 167 64 537 461 273 64 154 64 354 354 ...
output:
9828 545 8444 9817 7136 9828 9829 9328 9817 4735 7132 197 9822 6685 9807 9807 9839 197 545 9807 9807...
result:
ok 499971 tokens
Test #23:
score: 4
Accepted
time: 594ms
memory: 114628kb
input:
500000 261 10 261 301 261 180 10 241 241 498 498 265 261 388 388 561 241 25 265 331 265 63 561 156 2...
output:
7813 1 214 214 7975 7813 1 214 4642 7813 3789 7813 7813 7813 7813 214 214 6370 7813 417 7813 7576 21...
result:
ok 499903 tokens
Test #24:
score: 4
Accepted
time: 619ms
memory: 114556kb
input:
500000 12 21 12 30 21 53 21 58 12 75 53 14 30 40 14 72 53 26 58 67 75 42 14 66 14 29 72 71 42 49 71 ...
output:
8486 861 8486 8489 8799 8766 861 6790 1 6456 8770 8766 6530 805 861 8489 1 8218 1 8766 861 7274 8766...
result:
ok 499954 tokens
Test #25:
score: 4
Accepted
time: 613ms
memory: 118944kb
input:
500000 43 28 28 2 2 49 28 12 43 18 49 45 2 34 28 41 18 3 12 5 34 24 5 44 41 16 24 47 5 36 24 7 44 48...
output:
219 219 14064 14244 9577 9577 219 14056 14056 219 14244 10341 12054 5282 1 11259 8875 567 219 14056 ...
result:
ok 500000 tokens