QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299804#2728. Boring LecturesCamillus5 506ms31560kbC++203.3kb2024-01-07 09:44:242024-01-07 09:44:25

Judging History

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

  • [2024-01-07 09:44:25]
  • 评测
  • 测评结果:5
  • 用时:506ms
  • 内存:31560kb
  • [2024-01-07 09:44:24]
  • 提交

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';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 21412kb

input:

2 2 0
1 2

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 506ms
memory: 31560kb

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: 345ms
memory: 31552kb

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: 502ms
memory: 31452kb

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
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 2ms
memory: 21624kb

input:

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

output:

2

result:

wrong answer 2nd lines differ - expected: '1', found: ''

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%