| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 245754 | gs18115 | Holiday (IOI14_holiday) | C++14 | 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<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct node
{
int cnt;
ll sum;
int l,r;
node(){sum=0;cnt=l=r=0;}
}tree[1800010];
int tct;
void upd(int&n,int s,int e,int x,int p)
{
tree[++tct]=tree[n];
n=tct;
tree[n].cnt++;
tree[n].sum+=p;
if(s==e)
return;
int m=s+(e-s)/2;
if(x>m)
upd(tree[n].r,m+1,e,x,p);
else
upd(tree[n].l,s,m,x,p);
return;
}
ll query(int l,int r,int k)
{
if(k<=0)
return 0;
if(k>=tree[r].cnt-tree[l].cnt)
return tree[r].sum-tree[l].sum;
node&ln=tree[tree[l].r];
node&rn=tree[tree[r].r];
if(k>=rn.cnt-ln.cnt)
return(rn.sum-ln.sum)+query(tree[l].l,tree[r].l,k-(rn.cnt-ln.cnt));
return query(tree[l].r,tree[r].r,k);
}
int rt[100010];
int n,st,d;
ll ans;
void dnc1(int s,int e,int as,int ae)
{
if(s>e)
return;
int m=s+(e-s)/2;
int mxi=-1;
ll cans=-1;
for(int i=as;i<=ae;i++)
{
ll cur=query(rt[i-1],rt[m],d-(st+m-i*2));
if(cur>cans)
cans=cur,mxi=i;
}
ans=max(ans,cans);
dnc1(s,m-1,as,mxi);
dnc1(m+1,e,mxi,ae);
return;
}
void dnc2(int s,int e,int as,int ae)
{
if(s>e)
return;
int m=s+(e-s)/2;
int mxi=-1;
ll cans=-1;
for(int i=as;i<=ae;i++)
{
ll cur=query(rt[m-1],rt[i],d-(i*2-st-m));
if(cur>cans)
cans=cur,mxi=i;
}
ans=max(ans,cans);
dnc2(s,m-1,as,mxi);
dnc2(m+1,e,mxi,ae);
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>st>>d;
vector<int>v(n);
for(int&t:v)
cin>>t;
vector<int>cv=v;
sort(all(cv));
cv.erase(unique(all(cv)),cv.end());
int m=cv.size();
v.insert(v.begin(),0);
for(int i=0;i++<n;)
upd(rt[i]=rt[i-1],1,m,upper_bound(all(cv),v[i])-cv.begin(),v[i]);
dnc1(st,min(n,st+d-1),1,st);
dnc2(max(1,st-d+1),st,st,n);
cout<<ans<<endl;
return 0;
}