| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 52849 | zetapi | 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 <holiday.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<ll,ll> pii;
const int MAX=3e5;
struct data
{
ll ind;
ll sum;
} seg[MAX];
vector<pii> sorted;
ll N,D,Start,pos[MAX],R[MAX],f[MAX][2],g[MAX][2],fans[MAX][2],gans[MAX][2];
void build(int low,int high,int node)
{
if(low==high)
{
R[low]=delta;
if(low<=sorted.size())
{
seg[node].ind=1;
seg[node].sum=sorted[low-1].first;
}
else
{
seg[node].ind=0;
seg[node].sum=0;
}
return ;
}
int mid=(low+high)/2;
build(low,mid,2*node);
build(mid+1,high,2*node+1);
seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
return ;
}
void update(int low,int high,int node,int idx,int delta)
{
if(idx>sorted.size() or idx<1)
return ;
if(low==high)
{
R[row]=delta;
seg[node].ind=delta;
if(delta)
seg[node].sum=sorted[low-1].first;
else
seg[node].sum=0;
return ;
}
int mid=(low+high)/2;
if(idx>=low and idx<=mid)
update(low,mid,2*node,idx,delta);
else
update(mid+1,high,2*node+1,idx,delta);
seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
return ;
}
ll query(int low,int high,int node,int K)
{
if(low==high)
return seg[node].sum;
int mid=(low+high)/2;
if(seg[2*node].ind>=K)
return query(low,mid,2*node,K);
return seg[2*node].sum+query(mid+1,high,2*node+1,K-seg[2*node].ind);
}
ll cal(int idx,int qlow,int qhigh,int type)
{
int rem;
pii res=mp(0,-qlow);
//for(int A=qhigh+1;A<=N;A++)
update(1,N,1,pos[qhigh+1],0);
for(int A=qhigh;A>=qlow;A--)
{
rem=idx-(type+1)*(A-Start);
if(rem>0)
res=max(res,mp(query(1,N,1,rem),(ll)-A));
update(1,N,1,pos[A],0);
}
for(int A=qlow;A<=qhigh;A++)
update(1,N,1,pos[A],1);
fans[idx][type]=res.first;
return -res.second;
}
ll cal2(int idx,int qlow,int qhigh,int type)
{
int rem;
pii res=mp(0,qhigh);
//for(int A=1;A<qlow;A++)
update(1,N,1,pos[qlow-1],0);
for(int A=qlow;A<=qhigh;A++)
{
rem=idx-(type+1)*(Start-A);
if(rem>0)
res=max(res,mp(query(1,N,1,rem),(ll)A));
update(1,N,1,pos[A],0);
}
for(int A=qlow;A<=qhigh;A++)
update(1,N,1,pos[A],1);
gans[idx][type]=res.first;
return res.second;
}
void cal(int low,int high,int qlow,int qhigh,int type)
{
if(low>high)
return ;
int mid=(low+high)/2;
f[mid][type]=cal(mid,qlow,qhigh,type);
if(low==high)
{
for(int A=qlow+1;A<qhigh;A++)
update(1,N,1,pos[A],0);
return ;
}
cal(mid+1,high,f[mid][type],qhigh,type);
cal(low,mid-1,qlow,f[mid][type],type);
return ;
}
//#include <holiday.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<ll,ll> pii;
const int MAX=3e5;
struct data
{
ll ind;
ll sum;
} seg[MAX];
vector<pii> sorted;
ll N,D,Start,pos[MAX],R[MAX],f[MAX][2],g[MAX][2],fans[MAX][2],gans[MAX][2];
void build(int low,int high,int node)
{
if(low==high)
{
if(low<=sorted.size())
{
seg[node].ind=1;
seg[node].sum=sorted[low-1].first;
}
else
{
seg[node].ind=0;
seg[node].sum=0;
}
return ;
}
int mid=(low+high)/2;
build(low,mid,2*node);
build(mid+1,high,2*node+1);
seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
return ;
}
void update(int low,int high,int node,int idx,int delta)
{
if(idx>sorted.size() or idx<1)
return ;
if(low==high)
{
R[low]=delta;
seg[node].ind=delta;
if(delta)
seg[node].sum=sorted[low-1].first;
else
seg[node].sum=0;
return ;
}
int mid=(low+high)/2;
if(idx>=low and idx<=mid)
update(low,mid,2*node,idx,delta);
else
update(mid+1,high,2*node+1,idx,delta);
seg[node].ind=seg[2*node].ind+seg[2*node+1].ind;
seg[node].sum=seg[2*node].sum+seg[2*node+1].sum;
return ;
}
ll query(int low,int high,int node,int K)
{
if(low==high)
return seg[node].sum;
int mid=(low+high)/2;
if(seg[2*node].ind>=K)
return query(low,mid,2*node,K);
return seg[2*node].sum+query(mid+1,high,2*node+1,K-seg[2*node].ind);
}
ll cal(int idx,int qlow,int qhigh,int type)
{
int rem;
pii res=mp(0,-qlow);
//for(int A=qhigh+1;A<=N;A++)
update(1,N,1,pos[qhigh+1],0);
for(int A=qhigh;A>=qlow;A--)
{
rem=idx-(type+1)*(A-Start);
if(rem>0)
res=max(res,mp(query(1,N,1,rem),(ll)-A));
update(1,N,1,pos[A],0);
}
for(int A=qlow;A<=qhigh;A++)
update(1,N,1,pos[A],1);
fans[idx][type]=res.first;
return -res.second;
}
ll cal2(int idx,int qlow,int qhigh,int type)
{
int rem;
pii res=mp(0,qhigh);
//for(int A=1;A<qlow;A++)
update(1,N,1,pos[qlow-1],0);
for(int A=qlow;A<=qhigh;A++)
{
rem=idx-(type+1)*(Start-A);
if(rem>0)
res=max(res,mp(query(1,N,1,rem),(ll)A));
update(1,N,1,pos[A],0);
}
for(int A=qlow;A<=qhigh;A++)
update(1,N,1,pos[A],1);
gans[idx][type]=res.first;
return res.second;
}
void cal(int low,int high,int qlow,int qhigh,int type)
{
if(low>high)
return ;
int mid=(low+high)/2;
f[mid][type]=cal(mid,qlow,qhigh,type);
if(low==high)
{
for(int A=qlow+1;A<qhigh;A++)
update(1,N,1,pos[A],0);
return ;
}
cal(mid+1,high,f[mid][type],qhigh,type);
cal(low,mid-1,qlow,f[mid][type],type);
return ;
}
void cal2(int low,int high,int qlow,int qhigh,int type)
{
if(low>high)
return ;
int mid=(low+high)/2;
g[mid][type]=cal2(mid,qlow,qhigh,type);
if(low==high)
{
for(int A=qlow;A<qhigh;A++)
update(1,N,1,pos[A],0);
return ;
}
cal2(mid+1,high,qlow,g[mid][type],type);
cal2(low,mid-1,g[mid][type],qhigh,type);
return ;
}
ll find(int D)
{
ll res=0;
for(int A=0;A<=D;A++)
{
//cout<<A<<"\n";
//cout<<f[A][1]<<" hola "<<fans[A][1]<<"\n";
//cout<<g[A][1]<<" hola "<<gans[A][1]<<"\n";
res=max(res,fans[A][1]+gans[D-A][0]);
res=max(res,gans[A][1]+fans[D-A][0]);
}
return res;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[])
{
N=n;
D=d;
Start=start+1;
ll cur,res=0,tem=attraction[start];
attraction[start]=0;
for(int A=start;A<N;A++)
sorted.pb(mp(attraction[A],A+1));
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
for(int A=0;A<sorted.size();A++)
pos[sorted[A].second]=A+1;
build(1,N,1);
cal(1,D,Start,min(Start+D,N),0);
build(1,N,1);
cal(1,D,Start,min(Start+D,N),1);
sorted.clear();
for(int A=0;A<=start;A++)
sorted.pb(mp(attraction[A],A+1));
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
for(int A=0;A<sorted.size();A++)
pos[sorted[A].second]=A+1;
build(1,N,1);
cal2(1,D,max((ll)1,Start-D),Start,0);
build(1,N,1);
cal2(1,D,max((ll)1,Start-D),Start,1);
f[0][0]=Start;
f[0][1]=Start;
g[0][0]=Start;
g[0][1]=Start;
res=max(res,find(D));
res=max(res,tem+find(D-1));
return res;
}
/*int main()
{
ios_base::sync_with_stdio(false);
int n,d,s,attraction[100000]={10,2,20,30,1};
cout<<findMaxAttraction( n=5, s=2, d=7, attraction);
return 0;
}*/
//cout<<A<<"\n";
//cout<<f[A][1]<<" hola "<<fans[A][1]<<"\n";
//cout<<g[A][1]<<" hola "<<gans[A][1]<<"\n";
res=max(res,fans[A][1]+gans[D-A][0]);
res=max(res,gans[A][1]+fans[D-A][0]);
}
return res;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[])
{
N=n;
D=d;
Start=start+1;
ll cur,res=0,tem=attraction[start];
attraction[start]=0;
for(int A=start;A<N;A++)
sorted.pb(mp(attraction[A],A+1));
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
for(int A=0;A<sorted.size();A++)
pos[sorted[A].second]=A+1;
build(1,N,1);
cal(1,D,Start,min(Start+D,N),0);
build(1,N,1);
cal(1,D,Start,min(Start+D,N),1);
sorted.clear();
for(int A=0;A<=start;A++)
sorted.pb(mp(attraction[A],A+1));
sort(sorted.begin(),sorted.end());
reverse(sorted.begin(),sorted.end());
for(int A=0;A<sorted.size();A++)
pos[sorted[A].second]=A+1;
build(1,N,1);
cal2(1,D,max((ll)1,Start-D),Start,0);
build(1,N,1);
cal2(1,D,max((ll)1,Start-D),Start,1);
f[0][0]=Start;
f[0][1]=Start;
g[0][0]=Start;
g[0][1]=Start;
res=max(res,find(D));
res=max(res,tem+find(D-1));
return res;
}
/*int main()
{
ios_base::sync_with_stdio(false);
int n,d,s,attraction[100000]={10,2,20,30,1};
cout<<findMaxAttraction( n=5, s=2, d=7, attraction);
return 0;
}*/