Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#477#94. 「NOIP2021」报数Pigsyy1008001ms149072kbC++234.4kb2025-04-24 20:54:422025-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