QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#299804 | #2728. Boring Lectures | Camillus | 5 | 506ms | 31560kb | C++20 | 3.3kb | 2024-01-07 09:44:24 | 2024-01-07 09:44:25 |
Judging History
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;
}
详细
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%