#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();
auto ptr=it;
ptr--;
for(;;)
{
if(it==s.begin())
{
break;
}
it--;
int t=(*it).first+cam+1;
//auto it1=s.lower_bound({t,-1});
while((*ptr).first>=t)
{
if(ptr==s.begin())
{
ptr--;
break;
}
ptr--;
}
ptr++;
auto it1=ptr;
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()
{
alle.clear();
for(int i=0;i<K;++i)b[i].s.clear();
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-1)==0)
{
construct_whole();
}
return get_ans();
}
Compilation message
elephants.cpp: In function 'void construct_whole()':
elephants.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0;i<ve.size();++i)
| ~^~~~~~~~~~
elephants.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<=(ve.size()-1)/T;i++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
