#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
void sort_uniq(vector<T>& v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
struct Tree {
int i, j;
int v; ll s = 0;
int c = 0;
Tree *l, *r;
Tree(const vector<int>& vs, int i, int j): i(i), j(j), v(vs[i]) {
if (j - i == 1) {
l = r = nullptr;
} else {
int k = i + j >> 1;
l = new Tree(vs, i, k);
r = new Tree(vs, k, j);
}
}
void clear() {
s = 0;
c = 0;
if (l) l->clear(), r->clear();
}
void inc(int I) {
if (i <= I && I < j) {
c++;
if (l) {
l->inc(I);
r->inc(I);
s = l->s + r->s;
} else {
s += v;
}
}
}
ll get(int k, ll t = 0) {
tie(k, t) = _get(k, t);
return t;
}
pair<int,ll> _get(int k, ll t) {
if (k > 0 && c > 0) {
if (k >= c) {
t += s;
k -= c;
} else if (l) {
tie(k, t) = r->_get(k, t);
tie(k, t) = l->_get(k, t);
} else {
int u = min(k, c);
t += (ll)u * v;
k -= u;
}
}
return {k, t};
}
};
vector<ll> solve_all(vector<int> a, int x) {
vector<int> vals = a;
sort_uniq(vals);
unordered_map<int,int> vali;
for (int i = 0; i < vals.size(); i++) vali[vals[i]] = i;
for (int i = 0; i < a.size(); i++) a[i] = vali[a[i]];
vector<ll> wins((x + 1) * a.size(), -1);
vector<tuple<int,int,int,int>> layer, nlayer;
layer.emplace_back(0, wins.size() - 1, 0, a.size() - 1);
Tree available(vals, 0, vals.size());
int lay = 0;
while (!layer.empty()) {
available.clear();
int p = 0;
for (auto& lay : layer) {
int di, dj, ei, ej;
tie(di, dj, ei, ej) = lay;
assert(ei <= ej);
if (di > dj) continue;
int d = di + dj >> 1, e = -1;
for (int ee = ei; ee <= ej; ee++) {
while (p <= ee) available.inc(a[p++]);
ll w = available.get(d - x*ee);
if (wins[d] < w) {
wins[d] = w;
e = ee;
}
}
nlayer.emplace_back(di, d-1, ei, e);
nlayer.emplace_back(d+1, dj, e, ej);
}
layer = nlayer;
nlayer.clear();
}
return wins;
}
template<class T>
ll geet(const vector<T>& v, int i) {
return i < v.size() ? v[i] : v.back();
}
ll solve_right(int start, int d, const vector<int>& a) {
vector<int> l, r;
for (int i = start; i >= 0; i--) l.push_back(a[i]);
for (int i = start; i < a.size(); i++) r.push_back(a[i]);
r[0] = 0;
vector<ll> winl = solve_all(l, 2);
vector<ll> winr = solve_all(r, 1);
ll ans = 0;
for (int x = 0; x <= d; x++) {
ans = max(ans, geet(winl, x) + geet(winr, d - x));
}
return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<int> a(attraction, attraction + n);
ll ans = solve_right(start, d, a);
reverse(a.begin(), a.end());
return max(ans, solve_right(n - 1 - start, d, a));
}
Compilation message
holiday.cpp: In constructor 'Tree::Tree(const std::vector<int>&, int, int)':
holiday.cpp:21:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int k = i + j >> 1;
| ~~^~~
holiday.cpp: In function 'std::vector<long long int> solve_all(std::vector<int>, int)':
holiday.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < vals.size(); i++) vali[vals[i]] = i;
| ~~^~~~~~~~~~~~~
holiday.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < a.size(); i++) a[i] = vali[a[i]];
| ~~^~~~~~~~~~
holiday.cpp:89:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int d = di + dj >> 1, e = -1;
| ~~~^~~~
holiday.cpp:80:9: warning: unused variable 'lay' [-Wunused-variable]
80 | int lay = 0;
| ^~~
holiday.cpp: In function 'll solve_right(int, int, const std::vector<int>&)':
holiday.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i = start; i < a.size(); i++) r.push_back(a[i]);
| ~~^~~~~~~~~~
holiday.cpp: In instantiation of 'll geet(const std::vector<_Tp>&, int) [with T = long long int; ll = long long int]':
holiday.cpp:123:36: required from here
holiday.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | return i < v.size() ? v[i] : v.back();
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
18640 KB |
Output is correct |
| 2 |
Correct |
67 ms |
18608 KB |
Output is correct |
| 3 |
Correct |
83 ms |
18608 KB |
Output is correct |
| 4 |
Correct |
73 ms |
18624 KB |
Output is correct |
| 5 |
Correct |
371 ms |
18424 KB |
Output is correct |
| 6 |
Correct |
105 ms |
5096 KB |
Output is correct |
| 7 |
Correct |
203 ms |
9528 KB |
Output is correct |
| 8 |
Correct |
237 ms |
8756 KB |
Output is correct |
| 9 |
Correct |
74 ms |
3528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1580 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
15 ms |
1580 KB |
Output is correct |
| 4 |
Correct |
21 ms |
1580 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1324 KB |
Output is correct |
| 6 |
Correct |
6 ms |
768 KB |
Output is correct |
| 7 |
Correct |
5 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
16612 KB |
Output is correct |
| 2 |
Correct |
1151 ms |
48756 KB |
Output is correct |
| 3 |
Correct |
636 ms |
18212 KB |
Output is correct |
| 4 |
Correct |
18 ms |
1296 KB |
Output is correct |
| 5 |
Correct |
5 ms |
640 KB |
Output is correct |
| 6 |
Correct |
5 ms |
640 KB |
Output is correct |
| 7 |
Correct |
3 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1777 ms |
34688 KB |
Output is correct |
| 9 |
Correct |
1770 ms |
34724 KB |
Output is correct |
