| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 31150 | dongwon0427 | 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;
int n,st,d,Aidx[100005];
struct seg {
ll val;
int gaesu;
seg operator + (const seg &a) const {
seg ret;
ret.val = val + a.val; ret.gaesu=gaesu + a.gaesu;
return ret;
}
};
struct _tuple {int idx;ll val;};
seg segtree[400005];
_tuple A[100005];
void updt(int idx,int s,int e,int x,seg key) {
segtree[idx] = segtree[idx] + key;
if(s==e) return;
if(s<=x && x<=(s+e)/2) updt(idx*2,s,(s+e)/2,x,key);
else updt(idx*2+1,(s+e)/2+1,e,x,key);
}
ll ksum(int idx,int s,int e,int k) {
if(k<=0) return 0ll;
if(k >= segtree[idx].gaesu) return segtree[idx].val;
if(s==e) {
if(segtree[idx].gaesu==0 || k<=0) return 0ll;
return segtree[idx].val;
}
if( segtree[idx*2].gaesu < k ) return segtree[idx*2].val + ksum(idx*2+1,(s+e)/2+1,e,k-segtree[idx*2].gaesu);
return ksum(idx*2,s,(s+e)/2,k);
}
ll dodp(int s,int e,int p,int q) {
if(s>e) return 0;
int m = (s+e)/2;
for(int i=m;i<=e;i++) {
seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
int v=p; ll _max = 0;
for(int i=p;i<=q;i++) {
seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
ll tmpm = ksum(1,0,n-1,d - 2*(i-st) - (st-m));
if(_max < tmpm) {
v = i;
_max = tmpm;
}
}
for(int i=v;i<=q;i++) {
seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
for(int i=m;i<=e;i++) {
seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
ll ret1 = dodp(m+1,e,v,q);
for(int i=p;i<v;i++) {
seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
for(int i=m;i<=e;i++) {
seg tmp; tmp.gaesu=1;tmp.val=A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
ll ret2 = dodp(s,m-1,p,v);
for(int i=m;i<=e;i++) {
seg tmp; tmp.gaesu=-1;tmp.val=-A[i].val;
updt(1,0,n-1,Aidx[i],tmp);
}
ll ret = max({ret1,ret2,_max});
return ret;
}
ll straight(int idx) {
ll ret = 0;
for(int i=idx;i<n;i++) {
seg tmp; tmp.val = A[i].val; tmp.gaesu = 1;
updt(1,0,n-1,Aidx[i],tmp);
ret = max(ret,ksum(1,0,n-1,d - 2*(i-idx)));
}
for(int i=idx;i<n;i++) {
seg tmp; tmp.val = -A[i].val; tmp.gaesu = -1;
updt(1,0,n-1,Aidx[i],tmp);
}
return ret;
}
int main() {
scanf("%d%d%d",&n,&st,&d);
for(int i=0;i<n;i++) {
scanf("%lld",&A[i].val);
A[i].idx=i;
}
sort(A,A+n,[](_tuple a,_tuple b){return a.val > b.val;});
for(int i=0;i<n;i++) Aidx[A[i].idx]=i;
sort(A,A+n,[](_tuple a,_tuple b){return a.idx<b.idx;});
ll ans1 = dodp(0,st-1,st,n-1);
ll ans3 = straight(st);
sort(A,A+n,[](_tuple a,_tuple b){return a.idx>b.idx;});
for(int i=0;i<n/2;i++) swap(Aidx[i], Aidx[n-1-i]);
ll ans2 = dodp(0,n-st-2,n-st-1,n-1);
ll ans4 = straight(n-st-1);
printf("%lld\n",max({ans1,ans2,ans3,ans4}));
return 0;
}