QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299806#2728. Boring LecturesCamillus5 514ms31740kbC++203.7kb2024-01-07 09:47:402024-01-07 09:47:40

Judging History

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

  • [2024-01-07 09:47:40]
  • 评测
  • 测评结果:5
  • 用时:514ms
  • 内存:31740kb
  • [2024-01-07 09:47:40]
  • 提交

answer

/// @author Camillus <3
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;

static constexpr int maxn = 1 << 20;

int a[maxn];
int b[maxn];
int c[maxn];

inline int best(int i, int j) {
    if (a[i] > a[j]) {
        return i;
    } else {
        return j;
    }
}

namespace st1 {
    static constexpr int size = maxn;

    int tree[size * 2 - 1];

    void init() {
        for (int i = 0; i < size; i++) {
            int x = size + i - 1;
            tree[x] = i;
        }

        for (int x = size - 2; x >= 0; x--) {
            tree[x] = best(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    inline void up(int i) {
        int x = size + i - 1;

        while (x) {
            x = (x - 1) >> 1;
            tree[x] = best(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (l >= rx || lx >= r) {
            return 0;
        }

        if (l <= lx && rx <= r) {
            return tree[x];
        }

        return best(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
} // namespace st

namespace st2 {
    static constexpr int size = 1 << 20;

    int tree[size * 2 - 1];

    inline int comp(int i, int j) {
        if (c[i] > c[j]) {
            return i;
        } else {
            return j;
        }
    }

    void init() {
        for (int i = 0; i < size; i++) {
            int x = size + i - 1;
            tree[x] = i;
        }

        for (int x = size - 2; x >= 0; x--) {
            tree[x] = comp(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    inline void up(int i) {
        int x = size + i - 1;

        while (x) {
            x = (x - 1) >> 1;
            tree[x] = comp(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (l >= rx || lx >= r) {
            return 0;
        }

        if (l <= lx && rx <= r) {
            return tree[x];
        }

        return comp(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
} // namespace st2

int n, k;

int get_left(int i) {
    return st1::get(i - k + 1, i);
}

int get_right(int i) {
    return st1::get(i + 1, i + k);
}

inline void update(int i) {
    if (i == 1) {
        b[i] = get_right(i);
    } else if (i == n) {
        b[i] = get_left(i);
    } else {
        b[i] = best(
            get_left(i),
            get_right(i)
        );
    }

    c[i] = a[i] + a[b[i]];
    st2::up(i);
}

void build() {
    for (int i = 1; i <= n; i++) {
        update(i);
    }
}

int calc() {
    while (true) {
        int i = st2::tree[0];
        if (c[i] == a[i] + a[b[i]]) {
            return c[i];
        } else {
            update(i);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    st1::init();
    st2::init();

    int q;
    cin >> n >> k >> q;

    int K = 10000;

    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;

        a[i] = v;
        st1::up(i);
    }

    build();
    cout << calc() << '\n';

    while (q--) {
        int i, v;
        cin >> i >> v;

        a[i] = v;
        st1::up(i);

        if (q % K == 0) {
            build();
        }

        update(i);

        if (i != 1) {
            int j = get_left(i);
            update(j);
        }

        if (i != n) {
            int j = get_right(i);
            update(j);
        }

        cout << calc() << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 3ms
memory: 21660kb

input:

2 2 0
1 2

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 509ms
memory: 31740kb

input:

1000000 1000 0
500000 500000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

1000000

result:

ok single line: '1000000'

Test #3:

score: 0
Accepted
time: 378ms
memory: 31704kb

input:

1000000 1000000 0
191355930 876987865 740762203 911573173 931027199 669083148 113485206 783567981 385726820 965631761 525660572 128531760 964137166 863177871 877233053 544438109 232015540 881663296 70146553 105212329 289639683 455161711 925929162 443009947 663470749 806524289 692823640 47064079 3937...

output:

1999997187

result:

ok single line: '1999997187'

Test #4:

score: 0
Accepted
time: 514ms
memory: 31704kb

input:

1000000 1000 0
337169558 822795297 495342354 445458002 352974138 595967378 255683912 632668005 632403712 631080010 793258209 617835020 407863959 765546840 166847667 689855119 491829661 536156637 999860168 680191114 695227176 76498320 961778145 134881132 11031616 673250616 97820654 514929913 92811581...

output:

1999995708

result:

ok single line: '1999995708'

Subtask #2:

score: 0
Time Limit Exceeded

Test #5:

score: 10
Accepted
time: 6ms
memory: 20312kb

input:

2 2 4
1 1
1 0
1 2
2 0
2 2

output:

2
1
3
2
4

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 21208kb

input:

5 3 5
0 0 0 0 0
1 1000000000
4 1000000000
5 1000000000
2 1000000000
3 1000000000

output:

0
1000000000
1000000000
2000000000
2000000000
2000000000

result:

ok 6 lines

Test #7:

score: 0
Accepted
time: 199ms
memory: 21204kb

input:

10000 10000 100000
374349923 956237632 89016068 274930735 636575865 996622180 567384943 165470118 166531237 463361360 170343106 28457543 677745506 824660775 145777 539850687 890543804 370155199 412308677 17415343 321817814 625891363 120755544 322791725 724927588 308380690 513051546 115415871 7617902...

output:

1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999963687
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
1999939179
199...

result:

ok 100001 lines

Test #8:

score: 0
Accepted
time: 216ms
memory: 21604kb

input:

10000 100 100000
700281838 326539816 956048756 438471243 941669040 269256548 631534587 326670316 399177993 793091599 452020263 48305806 990696387 714086886 485618225 441330098 826446252 168128589 179038362 636200123 325270547 867047113 412076708 168835954 943311183 108666755 404345558 295196802 4153...

output:

1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
1999184767
199...

result:

ok 100001 lines

Test #9:

score: 0
Accepted
time: 199ms
memory: 21288kb

input:

10000 2 100000
510317059 403039171 658243298 506553376 986952936 582952128 257213011 47658551 840859110 116967292 909964596 477064650 947103518 94156490 47367833 576313585 862239668 665564199 669662425 16522409 182904914 945165871 376925711 657940304 280041893 695439653 309043866 471691053 202311903...

output:

1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
1987161005
198...

result:

ok 100001 lines

Test #10:

score: 0
Accepted
time: 227ms
memory: 21944kb

input:

10000 100 100000
180935983 45315330 593364757 318565692 420461707 652373530 867045249 711077432 316486457 111480477 129400585 621011744 914683230 200208135 945039620 265880048 568098467 412027124 298282636 170899976 852455093 698517927 504057602 332513965 917187014 471739526 129403528 111950215 1356...

output:

1999069491
1999069491
1999069491
1999069491
1999069491
1999069491
1999069491
1997961004
1997961004
1997961004
1997961004
1997402662
1997402662
1997402662
1997402662
1997402662
1997402662
1997402662
1997402662
1997352782
1997352782
1996559863
1996559863
1998461181
1998461181
2000000000
2000000000
200...

result:

ok 100001 lines

Test #11:

score: -10
Time Limit Exceeded

input:

10000 10000 100000
1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1000000000
999999999
999999998
999999997
999999996
999999995
999999994
999999993
999999992
999999991
999999990
999999989
999999988
999999987
999999986
999999985
999999984
999999983
999999982
999999981
999999980
999999979
999999978
999999977
999999976
999999975
999999974
999999973
999999972
999999971...

result:


Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%