QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297705#2728. Boring LecturesCamillus0 329ms78140kbC++202.1kb2024-01-05 02:48:022024-01-05 02:48:03

Judging History

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

  • [2024-01-05 02:48:03]
  • 评测
  • 测评结果:0
  • 用时:329ms
  • 内存:78140kb
  • [2024-01-05 02:48:02]
  • 提交

answer

/// @author Camillus <3
#ifndef LOCAL
#define debug(...) 42
#endif
#include "bits/stdc++.h"
using namespace std;

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

    int a[size];
    int tree[size * 2 - 1];

    inline int comp(int i, int j) {
        if (a[i] > a[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 set(int i, int v) {
        int x = size + i + 1;
        a[i] = v;

        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 st

int n, k;

set<tuple<int, int, int>, greater<>> b;

void build() {
    b.clear();
    auto a = st::a;
    for (int i = 1; i < n; i++) {
        int j = st::get(i + 1, i + k);
        b.emplace(a[i] + a[j], i, j);
    }
}

int calc() {
    auto a = st::a;
    while (true) {
        auto [v, i, j] = *b.begin();
        if (v != a[i] + a[j]) {
            b.erase(b.begin());
            b.emplace(a[i] + a[j], i, j);
        } else {
            return v;
        }
    }
}

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

    st::init();
    
    int q;
    cin >> n >> k >> q;

    int K = (int)ceill(min(sqrtl(n), sqrtl(q))) + 1;

    debug(K);

    auto a = st::a;

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

        st::set(i, v);
    }


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

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 4ms
memory: 12076kb

input:

2 2 0
1 2

output:

3

result:

ok single line: '3'

Test #2:

score: -5
Wrong Answer
time: 329ms
memory: 78140kb

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:

999999

result:

wrong answer 1st lines differ - expected: '1000000', found: '999999'

Subtask #2:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 4ms
memory: 13072kb

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:

0%