#include <bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = int(1e5) + 7;
typedef pair<ll, int> pii;
pii operator + (const pii& x, const pii& y) {
return pii(x.fi + y.fi, x.se + y.se);
}
struct TSegment {
vector<int> l, h;
vector<pii> st;
TSegment() {}
void init(int n) {
l.resize(4 * n + 4);
h.resize(l.size());
st.resize(l.size());
build(1, 0, n - 1);
}
void reset() {
fill(st.begin(), st.end(), pii(0, 0));
}
void build(int x, int low, int high) {
l[x] = low, h[x] = high, st[x] = pii(0, 0);
if(l[x] == h[x]) return;
int mid = low + high >> 1;
build(x << 1, low, mid);
build(x << 1 | 1, mid + 1, high);
}
void upd(int x, int pos, int val, int s) {
if(l[x] > pos || h[x] < pos) return;
if(l[x] == h[x]) {
st[x].fi += val;
st[x].se += s;
return;
}
upd(x << 1, pos, val, s);
upd(x << 1 | 1, pos, val, s);
st[x] = st[x << 1] + st[x << 1 | 1];
}
ll get(int x, int k) {
if(k < 0) return 0;
if(k >= st[x].se) return st[x].fi;
if(l[x] == h[x]) return 0;
if(st[x << 1].se >= k) return get(x << 1, k);
return st[x << 1].fi + get(x << 1 | 1, k - st[x << 1].se);
}
} it;
const int M = 3 * N;
ll f[2][M], g[2][M];
int s;
vector<int> id, pos, val;
int L = -1, R = -1;
pair<ll, ll> cost(int d, int l, int r) {
if(L == -1 && R == -1) L = l, R = L - 1;
while(L < l) it.upd(1, pos[L], -val[L], -1), ++L;
while(L > l) --L, it.upd(1, pos[L], val[L], 1);
while(R > r) it.upd(1, pos[R], -val[R], -1), --R;
while(R < r) ++R, it.upd(1, pos[R], val[R], 1);
return mp(it.get(1, d - r + l), it.get(1, d - 2 * (r - l)));
}
void dp(int cur, int l, int r, int optl, int optr) {
if(l > r || optl > optr) return;
int m = l + r >> 1, optm = optl;
ll cf, cg;
f[cur][m] = 0, g[cur][m] = 0;
for(int i = optl; i <= optr; ++i) {
tie(cf, cg) = cost(m, s, i);
if(cf > f[cur][m]) optm = i, f[cur][m] = cf;
if(cg > g[cur][m]) g[cur][m] = cg;
}
dp(cur, l, m - 1, optl, optm);
dp(cur, m + 1, r, optm, optr);
}
void dpg(int cur, int l, int r, int optl, int optr) {
if(l > r || optl > optr) return;
int m = l + r >> 1, optm = optl;
ll cf, cg;
g[cur][m] = 0;
for(int i = optl; i <= optr; ++i) {
tie(cf, cg) = cost(m, s, i);
if(cg > g[cur][m]) optm = i, g[cur][m] = cg;
}
dpg(cur, l, m - 1, optl, optm);
dpg(cur, m + 1, r, optm, optr);
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
val.resize(n); pos.resize(n);
id.resize(n); iota(id.begin(), id.end(), 0);
copy(attraction, attraction + n, val.begin());
sort(id.begin(), id.end(), [&](const int& x, const int& y) {
return val[x] > val[y];
});
for(int i = 0; i < n; ++i) pos[id[i]] = i;
it.init(n);
s = start + 1; dp(0, 0, d, s, n - 1);
dpg(0, 0, d, s, n - 1);
for(int i = n - 1; i >= 0; --i) val[i] = attraction[n - i - 1];
sort(id.begin(), id.end(), [&](const int& x, const int& y) {
return val[x] > val[y];
});
for(int i = 0; i < n; ++i) pos[id[i]] = i;
it.reset(); L = R = -1;
s = n - start - 1; dp(1, 0, d, s, n - 1);
dpg(1, 0, d, s, n - 1);
ll res = max(f[0][d - 1], f[1][d]);
for(int i = 0; i <= d; ++i){
if(d - i - 2 >= 0) {
res = max(res, g[0][i] + f[1][d - i - 2]);
}
if(d - i - 1 >= 0) res = max(res, f[0][i] + g[1][d - i - 1]);
}
return res;
}
//int a[N];
//
//int32_t main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// #define Task "test"
// if(fopen(Task".inp", "r")) {
// freopen(Task".inp", "r", stdin);
// freopen(Task".out", "w", stdout);
// }
// int n, start, d;
// cin >> n >> start >> d;
// for(int i = 0; i < n; ++i) cin >> a[i];
// cout << findMaxAttraction(n, start, d, a);
//}
Compilation message
holiday.cpp: In member function 'void TSegment::build(int, int, int)':
holiday.cpp:33:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = low + high >> 1;
~~~~^~~~~~
holiday.cpp: In function 'void dp(int, int, int, int, int)':
holiday.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1, optm = optl;
~~^~~
holiday.cpp: In function 'void dpg(int, int, int, int, int)':
holiday.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1, optm = optl;
~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1515 ms |
17620 KB |
Output is correct |
| 2 |
Correct |
1434 ms |
17656 KB |
Output is correct |
| 3 |
Correct |
1499 ms |
17656 KB |
Output is correct |
| 4 |
Correct |
1479 ms |
17656 KB |
Output is correct |
| 5 |
Correct |
2248 ms |
14584 KB |
Output is correct |
| 6 |
Correct |
553 ms |
9208 KB |
Output is correct |
| 7 |
Correct |
1014 ms |
8972 KB |
Output is correct |
| 8 |
Correct |
1270 ms |
9724 KB |
Output is correct |
| 9 |
Correct |
382 ms |
9976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
768 KB |
Output is correct |
| 2 |
Correct |
23 ms |
768 KB |
Output is correct |
| 3 |
Correct |
24 ms |
768 KB |
Output is correct |
| 4 |
Correct |
26 ms |
760 KB |
Output is correct |
| 5 |
Correct |
23 ms |
768 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
676 KB |
Output is correct |
| 9 |
Correct |
6 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1525 ms |
15288 KB |
Output is correct |
| 2 |
Correct |
1600 ms |
19220 KB |
Output is correct |
| 3 |
Correct |
800 ms |
5624 KB |
Output is correct |
| 4 |
Correct |
23 ms |
640 KB |
Output is correct |
| 5 |
Correct |
6 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
2339 ms |
12920 KB |
Output is correct |
| 9 |
Correct |
2286 ms |
12920 KB |
Output is correct |
