| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 37029 | petil | Holiday (IOI14_holiday) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll vi[100005], Ldir[100005], Rdir[100005];
int n, st, d, po[100005];
struct BIT{
vector<ll> tree;
vector<int> cnt;
BIT(){}
BIT(int V):tree(4*V), cnt(4*V){}
void update(int x, int L, int R, int idx, ll val, int flag){
if(idx<L ||R<idx)return;
if(L==R){
cnt[x]+=flag;
tree[x]+=flag*val;return;
}
int mid = (L+R)>>1;
if(idx<=mid)update(x+x, L, mid, idx, val, flag);
else update(x+x+1, mid+1, R, idx, val, flag);
tree[x] = tree[x+x] + tree[x+x+1];
cnt[x] = cnt[x+x] + cnt[x+x+1];
}
ll query(int x, int L, int R, int topk){
if(topk==0)return 0;
if(L==R){
return tree[x];
}
int mid = (L+R)>>1;
ll ret = 0;
if(cnt[x+x]<topk){
ret = tree[x+x];
return ret + query(x+x+1, mid+1, R, topk-cnt[x+x]);
}
else{
return query(x+x, L, mid, topk);
}
}
}bit;
void div_conq(int L, int R, int c1, int c2, ll dir[]){
if(L>R){
return;
}
if(c1==c2){
bit.update(1,1, n, po[c1], vi[c1], 1);
for(int i=L; i<=R; i++){
int tp = i - (c1-st);
tp = max(tp, 0);
dir[i] = bit.query(1, 1, n, tp);
}
bit.update(1, 1, n ,po[c1], vi[c1], -1);
return;
}
int T = (L+R)>>1;
ll ret = -1;
int pos = -1;
for(int i= c1; i<=c2; i++){
int tp = T - (i-st);
tp = max(tp, 0);
bit.update(1, 1, n, po[i], vi[i], 1);
ll ss = bit.query(1, 1, n, tp);
if(ret < ss){
ret = ss, pos = i;
}
}
dir[T] = ret;
for(int i=c1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], -1);
if(L==R)return;
div_conq(L, T-1, c1, pos, dir);
for(int i=c1; i<=pos-1; i++)bit.update(1, 1, n, po[i], vi[i], 1);
div_conq(T+1, R, pos, c2, dir);
}
void div_conq2(int L, int R, int c1, int c2, ll dir[]){
if(L>R){
return;
}
if(c1==c2){
bit.update(1,1, n, po[c1], vi[c1], 1);
for(int i=L; i<=R; i++){
int tp = i - 2*abs(c1-st);
tp = max(tp, 0);
dir[i] = bit.query(1, 1, n, tp);
}
bit.update(1, 1, n ,po[c1], vi[c1], -1);
return;
}
int T = (L+R)>>1;
ll ret = -1;
int pos = -1;
for(int i= c2; i>=c1; i--){
int tp = T - 2*abs(i-st);
tp = max(tp, 0);
bit.update(1, 1, n, po[i], vi[i], 1);
ll ss = bit.query(1, 1, n, tp);
if(ret < ss){
ret = ss, pos = i;
}
}
dir[T] = ret;
for(int i=c1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], -1);
if(L==R)return;
div_conq2(L, T-1, pos, c2, dir);
for(int i=pos+1; i<=c2; i++)bit.update(1, 1, n, po[i], vi[i], 1);
div_conq2(T+1, R, c1, pos, dir);
}
ll ans;
void go()
{
bit = BIT(n+5);
div_conq(1, d, st+1, n, Rdir);
bit = BIT(n+5);
div_conq2(1, d, 1, st-1, Ldir);
for(int i=0; i<=d; i++){
ans = max(ans, Ldir[i] + Rdir[d-i]);
if(i!=d)
ans = max(ans, Ldir[i] + Rdir[d-1-i] + vi[st]);
// cout<<i<<" " <<Ldir[i] <<" " <<Rdir[i]<<endl;
}
}
int main()
{
scanf("%d %d %d", &n, &st, &d);
vector<pair<int, int> > tmp;
for(int i=1; i<=n; i++){
scanf("%lld", &vi[i]);
tmp.push_back({-vi[i], i});
}
sort(tmp.begin(), tmp.end());
for(int i=0; i<(int)tmp.size(); i++){
po[tmp[i].second] = i+1;
}
go();
tmp.clear();
reverse(vi+1, vi+n+1);st = n+1-st;
for(int i=1; i<=n; i++){
tmp.push_back({-vi[i], i});
}
sort(tmp.begin(), tmp.end());
for(int i=0; i<(int)tmp.size(); i++){
po[tmp[i].second] = i+1;
}
go();
cout<<ans;
}