//#include<elephants.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<int,int> pii;
const int MAX=6e6;
const int ROOT=50;
vector<pii> blocks;
ll dp[MAX],BlockNumber[MAX],Index[1100][1100];
ll N,K,qcnt,ptr,start,pos[MAX],nxt[MAX],pre[MAX],covered[MAX],arr[MAX];
void recalculate(ll idx)
{
for(int A=1;Index[idx][A]>0;A++)
Index[idx][A]=0;
ll start_=blocks[idx].first,end_=blocks[idx].second,lol=start_,lop=1;
pre[start_]=0;
Index[idx][1]=start_;
for(int A=nxt[start_];A!=nxt[end_];A=nxt[A])
{
pre[A]=lol;
lol=A;
Index[idx][++lop]=A;
}
ll cov=end_,cnt=1;
for(int A=end_;A>0;A=pre[A])
{
if(arr[cov]-arr[A]>K)
{
cov=A;
++cnt;
}
dp[A]=cnt;
covered[A]=arr[end_]+dp[A]*K-(arr[end_]-arr[A]);
}
/*cout<<arr[end_]<<"\n";
for(int A=start;A>0;A=nxt[A])
cout<<arr[A]<<" ";
cout<<"\n";*/
return ;
}
void build()
{
blocks.clear();
ll lol=0;
for(int A=0;A<=ROOT;A++)
for(int B=0;Index[A][B]>0;B++)
Index[A][B]=0;
for(int A=start;A>0;A=nxt[A])
{
BlockNumber[A]=blocks.size();
Index[BlockNumber[A]][++lol]=A;
if(lol==ROOT or nxt[A]==0)
{
blocks.pb(mp(Index[BlockNumber[A]][1],A));
lol=0;
}
}
for(int A=0;A<blocks.size();A++)
recalculate(A);
return ;
}
void remove(ll idx,ll val)
{
if(idx==start)
{
start=nxt[start];
blocks[0].first=start;
recalculate(BlockNumber[idx]);
return ;
}
for(int A=start;nxt[A]>0;A=nxt[A])
{
if(nxt[A]==idx)
{
nxt[A]=nxt[nxt[A]];
if(idx==blocks[BlockNumber[idx]].first)
blocks[BlockNumber[idx]].first=nxt[A];
else if(idx==blocks[BlockNumber[idx]].second)
blocks[BlockNumber[idx]].second=A;
break;
}
}
recalculate(BlockNumber[idx]);
return ;
}
void insert(ll idx,ll val)
{
if(val<=arr[start])
{
nxt[idx]=start;
start=idx;
BlockNumber[idx]=0;
blocks[0].first=start;
recalculate(BlockNumber[idx]);
}
else
{
ll lol=start;
for(int A=start;A>0;A=nxt[A])
if(val>=arr[A])
lol=A;
nxt[idx]=nxt[lol];
nxt[lol]=idx;
BlockNumber[idx]=BlockNumber[lol];
if(lol==blocks[BlockNumber[lol]].second)
blocks[BlockNumber[lol]].second=idx;
recalculate(BlockNumber[idx]);
}
return ;
}
ll count(ll CurrentBlock,ll CoveredTill)
{
if(CurrentBlock>=blocks.size())
return 0;
ll low=1,high=699,mid,res=-1;
while(low<=high)
{
mid=(low+high)/2;
if(Index[CurrentBlock][mid]==0)
high=mid-1;
else if(arr[Index[CurrentBlock][mid]]<=CoveredTill)
res=Index[CurrentBlock][mid],
low=mid+1;
else
high=mid-1;
}
if(res==blocks[CurrentBlock].second)
return count(CurrentBlock+1,CoveredTill);
else if(res<0)
res=blocks[CurrentBlock].first;
else
res=nxt[res];
return dp[res]+count(CurrentBlock+1,covered[res]);
}
void init(int n,int l,int X[])
{
N=n;
K=l;
ptr=n;
start=1;
for(int A=1;A<=N;A++)
{
pos[A]=A;
nxt[A]=A+1;
arr[A]=X[A-1];
}
nxt[N]=0;
build();
return ;
}
int update(int i,int y)
{
if(N==1)
return 1;
++i;
++ptr;
++qcnt;
remove(pos[i],y);
pos[i]=ptr;
arr[ptr]=y;
insert(pos[i],y);
// if(qcnt%ROOT==0)
// {
// qcnt=0;
// build();
// }
for(int A=0;A<blocks.size()-1;A++)
assert(nxt[blocks[A].second]==blocks[A+1].first);
int cur=start;
for(int A=0;A<blocks.size();A++)
{
recalculate(A);
for(int B=1;Index[A][B]>0;B++)
{
assert(Index[A][B]==cur and arr[Index[A][B]]>=arr[Index[A][B-1]]);
cur=nxt[cur];
}
}
assert(cur==0);
return count(0,-1);
}
Compilation message
elephants.cpp: In function 'void build()':
elephants.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<blocks.size();A++)
~^~~~~~~~~~~~~~
elephants.cpp: In function 'long long int count(long long int, long long int)':
elephants.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(CurrentBlock>=blocks.size())
~~~~~~~~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:184:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<blocks.size()-1;A++)
~^~~~~~~~~~~~~~~~
elephants.cpp:187:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<blocks.size();A++)
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
688 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
688 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
688 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
688 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
688 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
688 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
688 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
688 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
