#include "elephants.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,x,las,a[202020],z[202020],te=1;
set<ll> st;
ll K;
ll ki[1010101];
ll ka[1010101];
ll LZ[1010101];
ll isi[1010101];
ll p[21][202020],toe=2;
map<ll,ll> me;
ll tum(ll aa)
{
if(me[aa]==0)
{
me[aa]=++toe;
isi[toe]=aa;
}
return me[aa];
}
/*ll cie(ll aa,ll bb)
{
if(aa==1)return 1;
return p[aa][bb];
if(bb==0)
{
// cout<<isi[aa]<<" "<<bb<<" "<<tum(cari(0,K,isi[aa],isi[aa],1))<<"\n";
return tum(cari(0,K,isi[aa],isi[aa],1));
}
else
{
return cie(cie(aa,bb-1),bb-1);
}
}*/
ll cari(ll aa,ll bb,ll cc,ll dd,ll ee);
void baru(ll aa,ll bb)
{
return ;
ll ii;
tum(aa);
//if(aa==0)
// return ;
if(aa==K)
{
for(ii=0;ii<=20;ii++)
p[ii][1]=1;
return ;
}
//cout<<LZ[aa]<<"\n";
//p[0][tum(aa)]=cari(0,K,aa,0,1);
p[0][tum(aa)]=tum(bb);
cari(0,K,isi[tum(aa)],0,1);
cari(0,K,isi[tum(bb)],0,1);
for(ii=1;ii<=20;ii++)
{
ll zai=cari(0,K,isi[p[ii-1][tum(aa)]],0,1);
//baru(isi[p[ii-1][tum(aa)]],zai);
p[ii][tum(aa)]=p[ii-1][p[ii-1][tum(aa)]];
cari(0,K,isi[p[ii][tum(aa)]],0,1);
// cout<<me[K]<<" "<<tum(K)<<"_ "<<ii<<" "<<aa<<" "<<bb<<" "<<tum(bb)<<" "<<tum(aa)<<" "<<p[ii][tum(aa)]<<"\n";
}
}
void turun(ll aa,ll bb,ll ee)
{
if(aa<bb)
{
if(LZ[ee]!=-1)
{
if(!ki[ee])ki[ee]=++te;
if(!ka[ee])ka[ee]=++te;
ll ce=(aa+bb)/2;
if(aa==ce&&LZ[ki[ee]]!=LZ[ee])
{
LZ[ki[ee]]=LZ[ee];
baru(aa,LZ[ee]);
}
if((ce+1)==bb&&LZ[ka[ee]]!=LZ[ee])
{
LZ[ka[ee]]=LZ[ee];
baru(ce+1,LZ[ee]);
}
LZ[ki[ee]]=LZ[ee];
LZ[ka[ee]]=LZ[ee];
}
LZ[ee]=-1;
}
else
{
// cout<<aa<<" "<<bb<<" "<<LZ[ee]<<" isi\n";
}
}
ll cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
turun(aa,bb,ee);
if(aa==bb)
{
//baru(aa,LZ[ee]);
return LZ[ee];
}
else
{
ll ce=(aa+bb)/2;
if(cc<=ce)
{
if(!ki[ee])ki[ee]=++te;
return cari(aa,ce,cc,dd,ki[ee]);
}
else
{
if(!ka[ee])ka[ee]=++te;
return cari(ce+1,bb,cc,dd,ka[ee]);
}
}
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
turun(aa,bb,ee);
if(bb<cc||dd<aa)
return ;
if(cc<=aa&&bb<=dd)
{
LZ[ee]=ff;
if(aa==bb)
baru(aa,LZ[ee]);
turun(aa,bb,ee);
}
else
{
ll ce=(aa+bb)/2;
if(!ki[ee])ki[ee]=++te;
if(!ka[ee])ka[ee]=++te;
upd(aa,ce,cc,dd,ki[ee],ff);
upd(ce+1,bb,cc,dd,ka[ee],ff);
}
}
void ganti(ll aa)
{
ll ii;
auto it=st.lower_bound(aa);
ll Z;
if(it==st.begin())
{
Z=0;
}
else
{
it--;
Z=*it;
}
upd(0,K,Z-x,aa-x-1,1,aa);
}
void init(int N, int L, int X[])
{
memset(LZ,-1,sizeof(LZ));
n = N;
x=L;
K=2000000001;
for(i=0;i<N;i++)
{
a[i]=X[i];
st.insert(a[i]);
}
me[K]=1;
isi[1]=K;
a[n]=K;
for(i=0;i<N;i++)
tum(a[i]);
st.insert(K);
for(i=0;i<N;i++)
ganti(a[i]);
ganti(K);
upd(1,0,K,K,K,1);
//cout<<"___"<<tum(K)<<"\n";
}
ll cak(ll aa)
{
// return 0;
ll ii,jaw=1,O=tum(aa);
//for(ii=0;ii<=n;ii++)
// cari(0,K,a[ii],a[ii],1);
//cout<<aa<<" "<<cari(0,K,aa,aa,1)<<"\n";
//cout<<aa<<" "<<tum(aa)<<" "<<cie(tum(aa),0)<<"\n";
cari(0,K,aa,aa,1);
/*
for(ii=20;ii>=0;ii--)
{
cari(0,K,isi[O],isi[O],1);
ll tem=p[ii][O];
//cout<<ii<<" "<<O<<" "<<tem<<"\n";
if(tem>1)
{
O=tem;
jaw+=(1<<ii);
}
}
return jaw;*/
if(aa==K)
return 0;
else
{
// return 1+cak(isi[p[0][O]]);
return 1+cak(cari(0,K,aa,0,1));
}
}
int update(int zai, int y)
{
tum(y);
st.erase(a[zai]);
auto it=st.lower_bound(a[zai]);
ganti(*it);
a[zai]=y;
st.insert(a[zai]);
ganti(a[zai]);
auto ita=st.lower_bound(0);
return cak(*ita);
}
Compilation message
elephants.cpp: In function 'void baru(ll, ll)':
elephants.cpp:62:6: warning: unused variable 'zai' [-Wunused-variable]
ll zai=cari(0,K,isi[p[ii-1][tum(aa)]],0,1);
^~~
elephants.cpp: In function 'void ganti(ll)':
elephants.cpp:146:5: warning: unused variable 'ii' [-Wunused-variable]
ll ii;
^~
elephants.cpp: In function 'll cak(ll)':
elephants.cpp:186:5: warning: unused variable 'ii' [-Wunused-variable]
ll ii,jaw=1,O=tum(aa);
^~
elephants.cpp:186:8: warning: unused variable 'jaw' [-Wunused-variable]
ll ii,jaw=1,O=tum(aa);
^~~
elephants.cpp:186:14: warning: unused variable 'O' [-Wunused-variable]
ll ii,jaw=1,O=tum(aa);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8340 KB |
Output is correct |
| 7 |
Execution timed out |
9012 ms |
15792 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8340 KB |
Output is correct |
| 7 |
Execution timed out |
9012 ms |
15792 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8320 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8340 KB |
Output is correct |
| 7 |
Execution timed out |
9012 ms |
15792 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
