QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297706 | #2728. Boring Lectures | Camillus | 0 | 410ms | 78140kb | C++20 | 2.1kb | 2024-01-05 02:49:58 | 2024-01-05 02:49:59 |
Judging History
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 + 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 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 - 2;
}
}
}
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: 0ms
memory: 12860kb
input:
2 2 0 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: -5
Wrong Answer
time: 410ms
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: 13320kb
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%