#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "holiday.h"
#else
#endif
struct ovo {
ovo() {
l = r = NULL;
c = 0;
x = 0;
}
ovo *l, *r;
int c;
ll x;
void P() {
if(!l) l = new ovo();
if(!r) r = new ovo();
x = l->x + r->x;
c = l->c + r->c;
}
void C(int a) {
if(a == 0) x = c = 0;
else x = a, c = 1;
}
};
struct spt {
spt() { }
void init(int _n) {
n = _n;
rt = NULL;
}
private:
int n;
ovo *rt;
// // // //
static void Ci(int l, int r, ovo *&t, int vl, int si) {
if(!t) t = new ovo();
if(l == r) return t->C(vl);
int m = l + r >> 1;
if(m >= si) Ci(l, m, t->l, vl, si);
else Ci(1 + m, r, t->r, vl, si);
t->P();
}
// // // //
static ll Xi(int l, int r, ovo *&t, int x) {
if(!t) return 0ll;
if(x >= t->c) return t->x;
int lc = (t->l ? t->l->c : 0);
ll lx = (t->l ? t->l->x : 0ll);
int m = l + r >> 1;
if(lc >= x) return Xi(l, m, t->l, x);
else return lx + Xi(1 + m, r, t->r, x - lc);
}
public:
// // // //
void C(int si, int vl) {
Ci(0, n - 1, rt, vl, si);
}
// // // //
void R(int si) {
C(si, 0);
}
// // // //
ll X(int x) {
return Xi(0, n - 1, rt, x);
}
} st;
const int N = 100005, D = N * 3;
int si[N], rw[N];
ll rv[2][2][D];
int sm, ub;
void DCC(int ld, int rd, int li, int ri) {
if(ld > rd || li > ri) return;
int md = ld + rd >> 1;
ll ap = 0;
int pi = li;
for(int i = li; i <= ri; ++i) {
int j = si[i];
st.C(j, rw[j]);
ll tp = 0;
int ds = i + 1;
if(ub) ds *= 2;
if(md - ds > 0) tp = st.X(md - ds);
if(tp > ap) {
ap = tp;
pi = i;
}
}
rv[sm][ub][md] = ap;
for(int i = ri; i >= pi; --i) {
st.R(si[i]);
}
DCC(md + 1, rd, pi, ri);
for(int i = pi - 1; i >= li; --i) {
st.R(si[i]);
}
DCC(ld, md - 1, li, pi);
}
ll findMaxAttraction(int n, int s, int d, int *a) {
st.init(n);
{
vector<pair<int, int>> v;
for(int i = s + 1; i < n; ++i) {
v.push_back({a[i], i - s - 1});
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for(int i = 0; i < n - s - 1; ++i) {
si[v[i].second] = i;
rw[i] = v[i].first;
}
}
sm = 0;
ub = 0;
if(n - s > 1) DCC(0, d, 0, n - s - 2);
ub = 1;
if(n - s > 1) DCC(0, d, 0, n - s - 2);
{
vector<pair<int, int>> v;
for(int i = 0; i < s; ++i) {
v.push_back({a[i], s - i - 1});
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for(int i = 0; i < s; ++i) {
si[v[i].second] = i;
rw[i] = v[i].first;
}
}
sm = 1;
ub = 0;
if(s) DCC(0, d, 0, s - 1);
ub = 1;
if(s) DCC(0, d, 0, s - 1);
ll dr = 0;
for(int i = 0; i <= d; ++i) {
dr = max(dr, rv[0][1][i] + rv[1][0][d - i]);
if(i ^ d) dr = max(dr, rv[0][1][i] + rv[1][0][d - i - 1] + a[s]);
// // // //
dr = max(dr, rv[1][1][i] + rv[0][0][d - i]);
if(i ^ d) dr = max(dr, rv[1][1][i] + rv[0][0][d - i - 1] + a[s]);
}
#ifdef wambule
for(int i = 0; i < 2; ++i) {
for(int j = 0; j < 2; ++j) {
for(int k = 0; k <= d; ++k) {
cout << "[] " << i << " " << j << " " << k << " " << rv[i][j][k] << endl;
}
}
}
#endif
return dr;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc = 2;
if(tc == 1) {
int n = 5;
int s = 2;
int d = 7;
int a[] = {10, 2, 20, 30, 1};
ll fp = findMaxAttraction(n, s, d, a);
cout << fp << endl;
} else if(tc == 2) {
int n = 5;
int s = 0;
int d = 7;
int a[] = {2, 1, 100, 1, 2};
ll fp = findMaxAttraction(n, s, d, a);
cout << fp << endl;
}
return 0;
}
#endif
Compilation message
holiday.cpp: In static member function 'static void spt::Ci(int, int, ovo*&, int, int)':
holiday.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int m = l + r >> 1;
| ~~^~~
holiday.cpp: In static member function 'static ll spt::Xi(int, int, ovo*&, int)':
holiday.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int m = l + r >> 1;
| ~~^~~
holiday.cpp: In function 'void DCC(int, int, int, int)':
holiday.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int md = ld + rd >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1288 ms |
14540 KB |
Output is correct |
| 2 |
Correct |
1233 ms |
14316 KB |
Output is correct |
| 3 |
Correct |
1287 ms |
14352 KB |
Output is correct |
| 4 |
Correct |
1226 ms |
14432 KB |
Output is correct |
| 5 |
Correct |
1673 ms |
12800 KB |
Output is correct |
| 6 |
Correct |
506 ms |
6284 KB |
Output is correct |
| 7 |
Correct |
848 ms |
7360 KB |
Output is correct |
| 8 |
Correct |
1051 ms |
8420 KB |
Output is correct |
| 9 |
Correct |
390 ms |
6216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
748 KB |
Output is correct |
| 2 |
Correct |
21 ms |
748 KB |
Output is correct |
| 3 |
Correct |
22 ms |
748 KB |
Output is correct |
| 4 |
Correct |
24 ms |
876 KB |
Output is correct |
| 5 |
Correct |
21 ms |
620 KB |
Output is correct |
| 6 |
Correct |
6 ms |
492 KB |
Output is correct |
| 7 |
Correct |
5 ms |
492 KB |
Output is correct |
| 8 |
Correct |
5 ms |
492 KB |
Output is correct |
| 9 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1307 ms |
14952 KB |
Output is correct |
| 2 |
Correct |
1398 ms |
14916 KB |
Output is correct |
| 3 |
Correct |
585 ms |
4108 KB |
Output is correct |
| 4 |
Correct |
18 ms |
620 KB |
Output is correct |
| 5 |
Correct |
5 ms |
492 KB |
Output is correct |
| 6 |
Correct |
5 ms |
492 KB |
Output is correct |
| 7 |
Correct |
5 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1900 ms |
7672 KB |
Output is correct |
| 9 |
Correct |
1987 ms |
7888 KB |
Output is correct |
