# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
731049 | ogibogi2004 | 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 "elephants.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int K=333;
int dp1[MAXN];
int dp2[MAXN];
int where[MAXN];
int where1[MAXN];
set<pair<int,int> >alle;
int cam;
struct bucket
{
set<pair<int,int> >s;
void compute()
{
auto it=s.end();
for(;;)
{
if(it==s.begin())
{
break;
}
it--;
int t=(*it).first+cam+1;
auto it1=s.lower_bound({t,-1});
if(it1==s.end())
{
dp1[(*it).second]=1;
dp2[(*it).second]=t-1;
}
else
{
dp1[(*it).second]=dp1[(*it1).second]+1;
dp2[(*it).second]=dp2[(*it1).second];
}
}
}
}b[K];
int n;
int get_ans()
{
int T=n/K+2;
int lastb=(n-1)/T;
int firstnz=-1;
for(int i=0;i<=lastb;i++)
{
if(b[i].s.size()==0)continue;
firstnz=i;
break;
}
int t=(*b[firstnz].s.begin()).second;
int last=dp2[t];
int ret=dp1[t];
//cout<<"starting from "<<t<<endl;
for(int i=firstnz+1;i<=lastb;i++)
{
if(b[i].s.size()==0)continue;
auto it=b[i].s.lower_bound({last+1,0});
if(it==b[i].s.end())continue;
last=dp2[(*it).second];
ret+=dp1[(*it).second];
}
return ret;
}
void construct_whole()
{
vector<pair<int,int> >ve;
for(int i=1;i<=n;i++)
{
ve.push_back({where[i],i});
}
sort(ve.begin(),ve.end());
int T=n/K+2;
for(int i=0;i<ve.size();i++)
{
alle.insert(ve[i]);
where[ve[i].second]=ve[i].first;
where1[ve[i].second]=i/T;
b[i/T].s.insert(ve[i]);
}
for(int i=0;i<=(ve.size()-1)/T;i++)
{
b[i].compute();
}
}
void init(int N, int L, int X[])
{
n = N;
cam = L;
for(int i=0;i<N;i++)
{
where[i+1]=X[i];
}
construct_whole();
}
int cnt=0;
int update(int i, int y)
{
i++;
int j=where1[i];
b[j].s.erase({where[i],i});
int T=n/K+2;
int lastb=(n-1)/T;
int new_j=lastb;
if((*b[1].s.begin()).first>y)
{
new_j=0;
}
else
{
for(int j=1;j<lastb;j++)
{
if((*b[j+1].s.begin()).first>y)
{
new_j=j;
break;
}
}
}
b[new_j].s.insert({y,i});
b[new_j].compute();
where[i]=y;
where1[i]=new_j;
if(j!=new_j)b[j].compute();
cnt++;
if(cnt%max(1,T-3)==0)
{
construct_whole();
}
return get_ans();
}