# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
856626 |
2023-10-04T06:33:32 Z |
kilkuwu |
Holiday (IOI14_holiday) |
C++17 |
|
39 ms |
65536 KB |
#ifndef LOCAL
#include "holiday.h"
#endif
#include <bits/stdc++.h>
#ifdef LOCAL
#include "C:\Users\Admin\Documents\GitHub\HSG\debug.hpp"
#else
#define dbg(...) ;
#endif
using i32 = int;
using i64 = long long;
#define nl '\n'
#define int i64
struct PersistentSegmentTree {
struct Node {
int left = 0, right = 0;
int64_t sum = 0;
int cnt = 0;
};
std::vector<Node> t;
std::vector<int> values;
PersistentSegmentTree(const std::vector<int>& a) : t(1), values(a) {}
int update(int k, int l, int r, int p, int d) {
int id = t.size();
t.emplace_back();
t[id] = t[k];
if (l == r) {
t[id].sum += 1LL * values[l] * d;
t[id].cnt += d;
} else {
int mid = (l + r) / 2;
if (p <= mid) {
t[id].left = update(t[id].left, l, mid, p, d);
} else {
t[id].right = update(t[id].right, mid + 1, r, p, d);
}
t[id].sum = t[t[id].left].sum + t[t[id].right].sum;
t[id].cnt = t[t[id].left].cnt + t[t[id].right].cnt;
}
return id;
}
int64_t query(int k1, int k2, int l, int r, int how_many) {
if (l == r) {
return 1LL * std::min(t[k2].cnt - t[k1].cnt, how_many) * values[l];
}
int mid = (l + r) / 2;
int cnt_right = t[t[k2].right].cnt - t[t[k1].right].cnt;
if (cnt_right >= how_many) {
return query(t[k1].right, t[k2].right, mid + 1, r, how_many);
}
int64_t sum = t[t[k2].right].sum - t[t[k1].right].sum;
return sum + query(t[k1].left, t[k2].left, l, mid, how_many - cnt_right);
}
int update(int k, int p, int d) {
return update(k, 0, values.size() - 1, p, d);
}
int64_t query(int k1, int k2, int how_many) {
return query(k1, k2, 0, values.size() - 1, how_many);
}
};
i64 findMaxAttraction(i32 n, i32 s, i32 d, i32 attraction[]) {
s++;
std::vector<int> a(n + 1);
std::vector<int> vals(n);
for (int i = 1; i <= n; i++) a[i] = attraction[i - 1], vals[i - 1] = a[i];
std::sort(vals.begin(), vals.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
auto get_id = [&](int x) -> int {
return std::lower_bound(vals.begin(), vals.end(), x) - vals.begin();
};
PersistentSegmentTree tree(vals);
std::vector<int> roots = {0};
for (int i = 1; i <= n; i++) {
roots.push_back(tree.update(roots.back(), get_id(a[i]), 1));
}
int64_t ans = 0;
auto go = [&](auto self, int ll, int lr, int rl, int rr) -> void {
if (ll > lr) return;
if (rl > rr) return;
int mid = (ll + lr) / 2;
// go from s to mid and thne
int64_t best = 0;
int pos = rr;
for (int r = rl; r <= rr; r++) {
int rem = d - (r - mid + std::min(s - mid, r - s));
if (rem > 0) {
int64_t cand = tree.query(roots[mid - 1], roots[r], rem);
if (cand > best) {
best = cand;
pos = r;
}
}
}
ans = std::max(ans, best);
self(self, ll, mid - 1, rl, pos);
self(self, mid + 1, lr, pos, rr);
};
go(go, 1, s, s, n);
return ans;
}
#ifdef LOCAL
signed main() {
freopen("inp", "r", stdin);
i32 n, s, d;
std::cin >> n >> s >> d;
i32 attraction[n];
for (int i = 0; i < n; i++) std::cin >> attraction[i];
std::cout << findMaxAttraction(n, s, d, attraction);
}
#endif // LOCAL
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
632 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
8396 KB |
Output is correct |
2 |
Correct |
11 ms |
8140 KB |
Output is correct |
3 |
Correct |
13 ms |
11976 KB |
Output is correct |
4 |
Correct |
13 ms |
12260 KB |
Output is correct |
5 |
Correct |
32 ms |
38580 KB |
Output is correct |
6 |
Correct |
10 ms |
10440 KB |
Output is correct |
7 |
Correct |
17 ms |
19400 KB |
Output is correct |
8 |
Correct |
20 ms |
19220 KB |
Output is correct |
9 |
Correct |
8 ms |
10184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3024 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
2 ms |
3024 KB |
Output is correct |
4 |
Correct |
4 ms |
3024 KB |
Output is correct |
5 |
Correct |
2 ms |
2004 KB |
Output is correct |
6 |
Correct |
1 ms |
1496 KB |
Output is correct |
7 |
Correct |
1 ms |
1492 KB |
Output is correct |
8 |
Correct |
1 ms |
1492 KB |
Output is correct |
9 |
Correct |
1 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
8136 KB |
Output is correct |
2 |
Runtime error |
39 ms |
65536 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |