QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358659#6533. Traveling in CellsPorNPtreeTL 2922ms208912kbC++173.3kb2024-03-19 22:10:112024-03-19 22:10:13

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 22:10:13]
  • 评测
  • 测评结果:TL
  • 用时:2922ms
  • 内存:208912kb
  • [2024-03-19 22:10:11]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int read()
{
    char c;
    while (!isdigit(c = getchar()));
    int x = c ^ '0';
    while (isdigit(c = getchar())) {
        x = (x << 3) + (x << 1) + (c ^ '0');
    }
    return x;
}

const int N = 5e5 + 5;

int n, a[N], b[N];
long long s[N];

void modify(int x, int y)
{
    for (int i = x; i <= n; i += i & -i) {
        s[i] += y;
    }
    return;
}

long long query(int x)
{
    long long s = 0;
    for (; x; x -= x & -x) {
        s += ::s[x];
    }
    return s;
}

long long query(int l, int r)
{
    return query(r) - query(l - 1);
}

unordered_map<int, int> S[1 << 20];

void build(int k, int l, int r)
{
    S[k].clear();
    for (int i = l; i <= r; ++i) {
        ++S[k][a[i]];
    }
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    return;
}

void modify(int k, int l, int r, int x, int y)
{
    --S[k][a[x]];
    ++S[k][y];
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        modify(k << 1, l, mid, x, y);
    } else {
        modify(k << 1 | 1, mid + 1, r, x, y);
    }
    return;
}

vector<int> ck;

int queryPre(int k, int l, int r, int x)
{
    int s = 0;
    for (int i = 0; i < (int)ck.size() && s != r - l + 1; ++i) {
        s += S[k][ck[i]];
    }
    if (s == r - l + 1) {
        return l;
    }
    if (!s) {
        return r + 1;
    }
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    if (mid >= x) {
        return queryPre(k << 1, l, mid, x);
    }
    int z = 0;
    if ((z = queryPre(k << 1 | 1, mid + 1, r, x)) == mid + 1) {
        return queryPre(k << 1, l, mid, x);
    }
    return z;
}

int queryNxt(int k, int l, int r, int x)
{
    int s = 0;
    for (int i = 0; i < (int)ck.size() && s != r - l + 1; ++i) {
        s += S[k][ck[i]];
    }
    if (s == r - l + 1) {
        return r;
    }
    if (!s) {
        return l - 1;
    }
    if (l == r) {
        return l;
    }
    int mid = (l + r) >> 1;
    if (mid < x) {
        return queryNxt(k << 1 | 1, mid + 1, r, x);
    }
    int z = 0;
    if ((z = queryNxt(k << 1, l, mid, x)) == mid) {
        return queryNxt(k << 1 | 1, mid + 1, r, x);
    }
    return z;
}

signed main()
{
    int T = read();
    while (T--) {
        int q;
        n = read(), q = read();
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            s[i] = 0;
        }
        for (int i = 1; i <= n; ++i) {
            b[i] = read();
            modify(i, b[i]);
        }
        build(1, 1, n);
        while (q--) {
            int opt = read(), x = read(), y = read();
            if (opt == 1) {
                modify(1, 1, n, x, y);
                a[x] = y;
            } else if (opt == 2) {
                modify(x, y - b[x]);
                b[x] = y;
            } else if (opt == 3) {
                ck.resize(y);
                for (int i = 0; i < y; ++i) {
                    scanf("%d", &ck[i]);
                }
                int t1 = queryPre(1, 1, n, x), t2 = queryNxt(1, 1, n, x);
                printf("%lld\n", query(t1, t2));
            }
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 61132kb

input:

2
5 10
1 2 3 1 2
1 10 100 1000 10000
3 3 1 3
3 3 2 2 3
2 5 20000
2 3 200
3 3 2 1 3
3 3 3 1 2 3
1 3 4
2 1 100000
1 2 2
3 1 2 1 2
4 1
1 2 3 4
1000000 1000000 1000000 1000000
3 4 4 1 2 3 4

output:

100
110
1200
21211
100010
4000000

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 241ms
memory: 61168kb

input:

20000
15 15
1 1 3 3 2 3 3 3 3 3 2 3 2 3 3
634593973 158136379 707704004 998369647 831633445 263092797 937841412 451774682 552617416 483763379 50360475 794662797 74247465 537217773 901809831
3 6 4 1 3 5 10
3 5 7 1 2 3 4 5 9 10
3 4 3 3 8 9
2 13 608033129
3 15 2 3 5
1 9 3
3 8 4 1 3 7 10
2 6 727472865
3...

output:

2689089686
8377825475
1706073651
1439027604
2689089686
792730352
8904867081
8904867081
8270273108
831633445
692051585
2782432626
697783016
883944422
184057757
287523250
184057757
696388752
184057757
1675459344
2667693025
2614711258
4006992373
1767091974
5348541057
5348541057
390631780
2290216252
942...

result:

ok 200062 numbers

Test #3:

score: 0
Accepted
time: 315ms
memory: 61520kb

input:

2000
150 150
8 3 8 8 8 6 8 4 2 7 6 8 8 5 8 7 7 8 5 6 8 8 6 8 8 8 8 7 8 6 6 8 8 8 6 2 3 4 8 8 7 8 5 8 2 6 8 7 8 8 6 8 6 8 3 8 8 8 8 4 7 8 7 3 7 6 7 5 5 8 6 8 8 6 3 8 6 7 6 8 8 7 4 8 6 7 8 7 7 7 7 8 8 8 8 2 5 2 8 8 6 7 6 3 8 8 7 8 8 8 6 6 8 6 6 7 5 8 8 8 7 8 7 7 6 8 8 8 8 8 8 6 5 7 5 5 8 7 8 7 7 7 6 5...

output:

4449391171
3290849667
852793841
5178673994
995994209
11431868919
4327723427
5071541023
3032743466
962345334
2997656427
4534278452
3851900075
3611231417
5071541023
1477584218
1299005818
1299005818
2145605244
854143763
886347565
2081234124
2333808475
2455955801
4179722063
2328504333
1473735464
4107685...

result:

ok 199987 numbers

Test #4:

score: 0
Accepted
time: 828ms
memory: 80036kb

input:

10
30000 30000
3 4 2 4 4 4 4 3 4 3 4 3 4 3 4 4 2 4 4 4 4 4 3 3 3 4 3 4 3 4 3 3 4 2 4 3 3 3 3 4 3 4 4 4 4 2 3 3 4 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 2 3 4 4 4 4 3 4 4 3 3 3 4 4 3 4 4 2 3 4 4 4 4 3 2 4 3 4 3 2 4 4 3 4 2 2 4 4 4 4 2 4 3 2 4 4 3 4 4 4 2 4 4 3 2 3 2 3 3 3 4 2 4 3 4 1 4 3 4 4 4...

output:

6959437173
934970676
72461245502
8365928740
8384151048
984567228
12482909122
1904927816
15134139942
3759040688
92670874909
332468911
5936663371
3562978848
1300592004
10314009201
5581540905
131246926443
15087184135864
4077066271
1124704817
1520626740
4388174158
744377942
2770411457
6231852240
1508724...

result:

ok 200135 numbers

Test #5:

score: 0
Accepted
time: 751ms
memory: 122264kb

input:

3
100000 100000
6 6 2 6 5 3 6 5 4 6 4 6 6 6 6 5 2 5 2 6 6 6 1 6 5 6 4 5 6 6 5 4 5 4 3 4 5 5 6 6 5 6 6 5 2 5 6 5 4 2 5 6 6 6 5 2 5 6 6 4 5 6 3 3 6 5 6 5 5 5 5 4 4 4 4 3 6 5 4 5 6 5 6 6 6 6 3 6 5 6 5 4 3 5 6 4 5 3 6 5 3 5 6 4 6 5 4 5 5 5 2 5 4 6 6 3 5 5 5 5 5 4 5 5 6 5 5 6 6 6 5 5 4 6 5 4 4 2 6 6 6 5 ...

output:

753014823
938372065
5655899645
168297301
14372254310
1066586326
3520855082
2591792266
2321844837
64378192092
250581310
1845085639
1402247975
198007248
2157074263
2743531397
3433471688
10332600792
1085086491
4845484125
50019185900042
4036199358
154762798
50019185900042
1221387905
11240790307
10537215...

result:

ok 199749 numbers

Test #6:

score: 0
Accepted
time: 2922ms
memory: 208912kb

input:

3
100000 100000
173 276 418 362 183 321 401 316 193 426 212 126 206 409 382 443 405 412 259 233 356 355 340 41 354 447 421 464 436 436 329 239 427 415 452 424 174 294 220 413 293 456 140 304 438 462 418 345 160 296 443 234 455 452 396 347 438 413 235 416 363 186 340 285 340 457 392 359 451 310 431 1...

output:

832547880
1825993219
676042867
310750190
650714631
657481975
1279322
838513014
453432678
940357183
846050641
631145680
278723792
689448062
154699248
45678908
56518237
839298643
611124630
499104412
324172054
742064269
626600147
728123335
602272914
45485542
868574266
876207167
342300121
917221167
7055...

result:

ok 200119 numbers

Test #7:

score: -100
Time Limit Exceeded

input:

3
100000 100000
66046 49249 42478 61684 59308 38366 66208 38769 50465 63701 50193 47811 50312 56793 58616 63383 58390 17546 23446 57532 59030 63009 62771 46338 52747 54677 68893 58360 56617 42330 65075 51193 65417 67035 54247 54323 39404 61892 42821 30094 67958 46206 53273 28507 65864 42364 64063 46...

output:

787181803
340358691
794440759
970166774
501256821
822531703
505349238
299646179
317091968
718901636
589846615
490283989
1183290
98835675
715091970
941598117
81757251
249078591
559980949
587721512
408541247
542135558
217103011
916103998
422219165
786665928
215595722
309683697
275650079
660176857
9707...

result: