#include"holiday.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const Int N = 1e5+5;
int sz;
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
struct Segtree{
Int sum[8*N]; int cnt[8*N];
void reset(){
rep(v,0,2*sz) sum[v] = cnt[v] = 0;
}
void upd(int i,Int x,int v=0,int tl=0,int tr=sz-1){
assert(v<8*N);
// if(v==0) cout << i _ x << nl;
if(tl==tr){
sum[v] = x; cnt[v] = 1; return;
}
if(i<=mid) upd(i,x, lc,tl,mid);
else upd(i,x, rc,mid+1,tr);
sum[v] = sum[lc] + sum[rc];
cnt[v] = cnt[lc] + cnt[rc];
}
// query sum of largest k values
Int qry(int k,int v=0,int tl=0,int tr=sz-1){
assert(v<8*N);
if(k <= 0) return 0;
if(cnt[v] <= k) return sum[v];
Int kr = min(k, cnt[rc]);
return qry(k-kr, lc,tl,mid) + qry(kr, rc,mid+1,tr);
}
} segtree;
#undef mid
// what to check at index i
V<int> chk[4*N];
// parent interval
int chkl[4*N], chkr[4*N];
int lastl[4*N], lastr[4*N];
bool bsolved[4*N];
V<Int> solve(const V<Int>& a){
sz = (int)a.size();
// dbg(sz);
V<Int> ret(2*sz,0);
V<int> last(2*sz,0);
// sort and find its order
V<int> iord(sz);
{
V<int> ord(sz);
rep(i,0,sz) ord[i] = i;
sort(all(ord),[&](int i,int j){
return a[i] < a[j];
});
rep(i,0,sz) iord[ord[i]] = i;
}
// for(Int i : iord) cout << i << " ";
// cout << nl;
chkl[sz] = 0; chkr[sz] = 2*sz-1;
lastl[sz] = 0; lastr[sz] = sz-1;
rep(i,lastl[sz],lastr[sz]+1) chk[i].push_back(sz);
int repcnt = 0;
while(1){
repcnt++;
// dbg(repcnt);
assert(repcnt < 30);
segtree.reset();
set<int> solved;
rep(i,0,sz){
segtree.upd(iord[i],a[i]);
assert(i < 2*N);
while(!chk[i].empty()){
// assert((int)chk[i].size() > 0);
// dbg(chk[i].back());
int j = chk[i].back(); chk[i].pop_back();
bsolved[j] = 1;
// dbg(j);
// dbg(solved.size());
solved.insert(j);
// if(solved.empty() || solved.back()!=j){
// solved.push_back(j);
// }
Int x = segtree.qry(j-i);
if(x > ret[j]){
ret[j] = x; last[j] = i;
}
}
// dbg(i);
assert(chk[i].empty());
// chk[i] = V<int>();
}
// dbg(segtree.qry(3));
// break;
bool cont = 0;
int contcnt = 0;
for(int j : solved){
// dbg(j);
// cout << chkl[j] _ chkr[j] << nl;
cont |= chkl[j] != chkr[j];
if(chkl[j] < j){
int m = (chkl[j] + j-1)/2;
assert(m < j);
// dbg(m);
cont = 1;
chkl[m] = chkl[j]; chkr[m] = j-1;
lastl[m] = lastl[j]; lastr[m] = last[j];
rep(i,lastl[m],lastr[m]+1){
contcnt++;
chk[i].push_back(m);
}
}
if(j < chkr[j]){
int m = (j+1 + chkr[j])/2;
assert(j < m);
// dbg(m);
cont = 1;
chkl[m] = j+1; chkr[m] = chkr[j];
lastl[m] = last[j]; lastr[m] = lastr[j];
rep(i,lastl[m],lastr[m]+1){
contcnt++;
chk[i].push_back(m);
}
}
}
// dbg(contcnt);
// dbg(solved.size());
// if(contcnt==400004) for(int j : solved){
// dbg(j);
// // if(chkl[j] < j){
// // int m = (chkl[j] + j-1)/2;
// // dbg(m);
// // dbg(chkl[m]); dbg(chkr[m]);
// // dbg(lastl[m]); dbg(lastr[m]);
// // }
// // if(j < chkr[j]){
// // int m = (j+1 + chkr[j])/2;
// // dbg(m);
// // dbg(chkl[m]); dbg(chkr[m]);
// // dbg(lastl[m]); dbg(lastr[m]);
// // }
// }
if(!cont) break;
}
// Int prv = 0;
// for(Int x : ret){
// assert(prv <= x); prv = x;
// }
return ret;
}
Int findMaxAttraction(int n,int s,int d,int a[]){
Int ans = 0;
// V<Int> v = {20,0,2,0,10};
// for(Int x : v) cout << x << " ";
// cout << nl;
// for(Int x : solve(v)) cout << x << " ";
// cout << nl;
// return ans;
rep(loop,0,2){
V<Int> vl = {0};
for(int i=s-1; i>=0; i--){
vl.push_back(a[i]);
}
V<Int> vr = {a[s]};
for(int i=s+1; i<n; i++){
vr.push_back(0);
vr.push_back(a[i]);
}
vl = solve(vl);
// if(vl.empty()) vl = {0};
// dbg(l.size());
// for(Int x : l) cout << x << " ";
// cout << nl;
// dbg(vl.size());
// for(Int x : vl) cout << x << " ";
// cout << nl << nl;
vr = solve(vr);
// if(vr.empty()) vr = {0};
// dbg(r.size());
// for(Int x : r) cout << x << " ";
// cout << nl;
// dbg(vr.size());
// for(Int x : vr) cout << x << " ";
// cout << nl << nl;
// go right, then left
for(Int dl=0,dr=d; dr>=0; dl++,dr--){
Int ansl = dl<(Int)vl.size() ? vl[dl] : vl.back();
Int ansr = dr<(Int)vr.size() ? vr[dr] : vr.back();
ans = max(ans, ansl+ansr);
}
// dbg(ans);
// reverse all
reverse(a,a+n);
s = n-1-s;
// cout << nl << nl;
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
10068 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10068 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10068 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10068 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10096 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10068 KB |
Output is correct |
| 7 |
Correct |
6 ms |
10068 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1472 ms |
41448 KB |
Output is correct |
| 2 |
Correct |
805 ms |
42152 KB |
Output is correct |
| 3 |
Correct |
1581 ms |
41660 KB |
Output is correct |
| 4 |
Correct |
823 ms |
42320 KB |
Output is correct |
| 5 |
Correct |
1688 ms |
39848 KB |
Output is correct |
| 6 |
Correct |
401 ms |
19524 KB |
Output is correct |
| 7 |
Correct |
853 ms |
26656 KB |
Output is correct |
| 8 |
Correct |
1022 ms |
31600 KB |
Output is correct |
| 9 |
Correct |
291 ms |
16748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
11048 KB |
Output is correct |
| 2 |
Correct |
30 ms |
10956 KB |
Output is correct |
| 3 |
Correct |
33 ms |
11176 KB |
Output is correct |
| 4 |
Correct |
32 ms |
10836 KB |
Output is correct |
| 5 |
Correct |
28 ms |
10772 KB |
Output is correct |
| 6 |
Correct |
13 ms |
10360 KB |
Output is correct |
| 7 |
Correct |
13 ms |
10352 KB |
Output is correct |
| 8 |
Correct |
15 ms |
10224 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10324 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1480 ms |
41364 KB |
Output is correct |
| 2 |
Correct |
1580 ms |
41356 KB |
Output is correct |
| 3 |
Correct |
661 ms |
21824 KB |
Output is correct |
| 4 |
Correct |
32 ms |
10620 KB |
Output is correct |
| 5 |
Correct |
14 ms |
10348 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10240 KB |
Output is correct |
| 7 |
Correct |
16 ms |
10304 KB |
Output is correct |
| 8 |
Correct |
1623 ms |
28408 KB |
Output is correct |
| 9 |
Correct |
1669 ms |
28376 KB |
Output is correct |
