#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
//int T=2,B=150000/T+3;
int T=387,B=150000/T+3;
int a,b,c,d,e,i,j,ii,jj,zx,xc,L,lef,rig,mid,k[150009],f[150009],C,D,cnt,II,JJ,pas;
vector <int> v[150009],vv;
vector <pair <int, int> > dp[150009];
void REBL(int q){
int lef,rig,mid,h=q,hh;
dp[h].resize(v[h].size());
if(v[h].size()==0) return;
for(hh=v[h].size()-1; hh>=0; hh--){
lef=hh;rig=v[h].size();
while(lef+1<rig){
mid=((lef+rig)>>1);
if(v[h][mid]>v[h][hh]+L){
rig=mid;
}else{
lef=mid;
}
}
if(rig==v[h].size()){
dp[h][hh]={1,v[h][hh]+L};
}else{
dp[h][hh]=dp[h][rig];dp[h][hh].first++;
}
}
}
void REDO(){
int lef,rig,mid;
int h=0,hh=0,qw=0;vv.clear();
for(h=1; h<=B; h++){
for(hh=0; hh<v[h].size(); hh++){
vv.push_back(v[h][hh]);
}
v[h].clear();
}
qw=0;
for(h=0; h<vv.size(); h++){
if(h%T==0) qw++;
v[qw].push_back(vv[h]);
}
for(h=1; h<=B; h++){
k[h]=k[h-1];
if(v[h].size()==0) continue;
k[h]=v[h][v[h].size()-1];
/*dp[h].resize(v[h].size());
for(hh=v[h].size()-1; hh>=0; hh--){
lef=hh;rig=v[h].size();
while(lef+1<rig){
mid=((lef+rig)>>1);
if(v[h][mid]>v[h][hh]+mid){
rig=mid;
}else{
lef=mid;
}
}
if(rig==v[h].size()){
dp[h][hh]={1,v[h][hh]+mid};
}else{
dp[h][hh]=dp[h][rig+1];dp[h][hh].first++;
}
}*/
REBL(h);
/*cout<<h<<" "<<k[h]<<" "<<v[h].size()<<" "<<dp[h][0].first<<" "<<dp[h][0].second<<"\n";
exit(0);*/
}
k[B]=1000000003;
}
void init(int NN, int LL, int XX[]){
a=NN;L=LL;
for(i=1; i<=a; i++){
v[1].push_back(XX[i-1]);
f[i]=XX[i-1];
}
REDO();
/*cout<<v[1].size()<<"\n";
exit(0);*/
}
int fnd(int q){
int lef,rig,mid;
lef=0;rig=B+1;
while(lef+1<rig){
mid=((lef+rig)>>1);
if(k[mid]>=q){
rig=mid;
}else{
lef=mid;
}
}
return rig;
}
int fndbl(int q, int w){
int lef,rig,mid;
lef=-1;rig=v[q].size();
while(lef+1<rig){
mid=((lef+rig)>>1);
if(v[q][mid]>=w){
rig=mid;
}else{
lef=mid;
}
}
return rig;
}
int update(int Ii, int Yy){
int h,hh;
Ii++;
i=Ii;D=Yy;C=f[i];cnt++;
ii=fnd(C);e=0;
if(k[ii]==C){
if(v[ii].size()==0||v[ii][v[ii].size()-1]!=C){
ii++;II=0;e=1;
}
}
if(e==0){
II=fndbl(ii,C);
}
/*if(cnt==5){
cout<<v[1].size()<<"\n";
for(h=0; h<v[1].size(); h++){
cout<<v[1][h]<<" ";
}
cout<<"\n";
cout<<v[B].size()<<"\n";
for(h=0; h<v[B].size(); h++){
cout<<v[B][h]<<" ";
}
cout<<"\n";
cout<<i<<" "<<C<<" "<<ii<<" "<<II<<" "<<e<<"\n";
//exit(0);
}*/
v[ii].erase(v[ii].begin()+II);
jj=fnd(D);
JJ=fndbl(jj,D);
v[jj].insert(v[jj].begin()+JJ,D);
/*
if(cnt==5){
cout<<i<<" "<<D<<" "<<jj<<" "<<JJ<<"\n";
exit(0);
}
*/
REBL(ii);REBL(jj);
if(cnt%T==0) REDO();
f[i]=D;
/*
if(cnt==5){
cout<<v[1].size()<<"\n";
for(h=0; h<v[1].size(); h++){
cout<<v[1][h]<<" ";
}
cout<<"\n";
cout<<v[B].size()<<"\n";
for(h=0; h<v[B].size(); h++){
cout<<v[B][h]<<" ";
}
cout<<"\n";
}
*/
II=-2;pas=0;
for(h=1; h<=B; h++){
if(v[h].size()==0) continue;
c=fndbl(h,II+1);
/*if(cnt==5){
cout<<h<<" "<<II<<" "<<c<<"\n";
}*/
if(c==v[h].size()){
continue;
}
pas+=dp[h][c].first;II=dp[h][c].second;
//cout<<dp[h][c].first<<" "<<dp[h][c].second<<"\n";
}
return pas;
}
Compilation message
elephants.cpp: In function 'void REBL(int)':
elephants.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if(rig==v[h].size()){
| ~~~^~~~~~~~~~~~~
elephants.cpp: In function 'void REDO()':
elephants.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(hh=0; hh<v[h].size(); hh++){
| ~~^~~~~~~~~~~~
elephants.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(h=0; h<vv.size(); h++){
| ~^~~~~~~~~~
elephants.cpp:31:6: warning: unused variable 'lef' [-Wunused-variable]
31 | int lef,rig,mid;
| ^~~
elephants.cpp:31:10: warning: unused variable 'rig' [-Wunused-variable]
31 | int lef,rig,mid;
| ^~~
elephants.cpp:31:14: warning: unused variable 'mid' [-Wunused-variable]
31 | int lef,rig,mid;
| ^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:171:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | if(c==v[h].size()){
| ~^~~~~~~~~~~~~
elephants.cpp:108:8: warning: unused variable 'hh' [-Wunused-variable]
108 | int h,hh;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7388 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7388 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7388 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
654 ms |
9332 KB |
Output is correct |
8 |
Correct |
676 ms |
9628 KB |
Output is correct |
9 |
Correct |
654 ms |
11316 KB |
Output is correct |
10 |
Correct |
720 ms |
10764 KB |
Output is correct |
11 |
Correct |
646 ms |
10700 KB |
Output is correct |
12 |
Correct |
917 ms |
11288 KB |
Output is correct |
13 |
Correct |
1008 ms |
10552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7388 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
654 ms |
9332 KB |
Output is correct |
8 |
Correct |
676 ms |
9628 KB |
Output is correct |
9 |
Correct |
654 ms |
11316 KB |
Output is correct |
10 |
Correct |
720 ms |
10764 KB |
Output is correct |
11 |
Correct |
646 ms |
10700 KB |
Output is correct |
12 |
Correct |
917 ms |
11288 KB |
Output is correct |
13 |
Correct |
1008 ms |
10552 KB |
Output is correct |
14 |
Correct |
939 ms |
10460 KB |
Output is correct |
15 |
Correct |
1008 ms |
10468 KB |
Output is correct |
16 |
Correct |
1492 ms |
11980 KB |
Output is correct |
17 |
Correct |
1483 ms |
13112 KB |
Output is correct |
18 |
Correct |
1689 ms |
12808 KB |
Output is correct |
19 |
Correct |
1174 ms |
12396 KB |
Output is correct |
20 |
Correct |
1476 ms |
12884 KB |
Output is correct |
21 |
Correct |
1452 ms |
12880 KB |
Output is correct |
22 |
Correct |
1671 ms |
11828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
5 ms |
7388 KB |
Output is correct |
3 |
Correct |
4 ms |
7380 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
654 ms |
9332 KB |
Output is correct |
8 |
Correct |
676 ms |
9628 KB |
Output is correct |
9 |
Correct |
654 ms |
11316 KB |
Output is correct |
10 |
Correct |
720 ms |
10764 KB |
Output is correct |
11 |
Correct |
646 ms |
10700 KB |
Output is correct |
12 |
Correct |
917 ms |
11288 KB |
Output is correct |
13 |
Correct |
1008 ms |
10552 KB |
Output is correct |
14 |
Correct |
939 ms |
10460 KB |
Output is correct |
15 |
Correct |
1008 ms |
10468 KB |
Output is correct |
16 |
Correct |
1492 ms |
11980 KB |
Output is correct |
17 |
Correct |
1483 ms |
13112 KB |
Output is correct |
18 |
Correct |
1689 ms |
12808 KB |
Output is correct |
19 |
Correct |
1174 ms |
12396 KB |
Output is correct |
20 |
Correct |
1476 ms |
12884 KB |
Output is correct |
21 |
Correct |
1452 ms |
12880 KB |
Output is correct |
22 |
Correct |
1671 ms |
11828 KB |
Output is correct |
23 |
Correct |
4101 ms |
19612 KB |
Output is correct |
24 |
Correct |
4432 ms |
19644 KB |
Output is correct |
25 |
Correct |
3207 ms |
19216 KB |
Output is correct |
26 |
Correct |
3786 ms |
18544 KB |
Output is correct |
27 |
Correct |
4906 ms |
18336 KB |
Output is correct |
28 |
Correct |
3480 ms |
12264 KB |
Output is correct |
29 |
Correct |
3545 ms |
12256 KB |
Output is correct |
30 |
Correct |
3468 ms |
12252 KB |
Output is correct |
31 |
Correct |
3586 ms |
12264 KB |
Output is correct |
32 |
Correct |
4050 ms |
17924 KB |
Output is correct |
33 |
Correct |
3351 ms |
17260 KB |
Output is correct |
34 |
Correct |
3902 ms |
18140 KB |
Output is correct |
35 |
Correct |
3943 ms |
20860 KB |
Output is correct |
36 |
Correct |
5135 ms |
17900 KB |
Output is correct |
37 |
Correct |
3682 ms |
20328 KB |
Output is correct |
38 |
Correct |
5256 ms |
17136 KB |
Output is correct |
39 |
Correct |
3484 ms |
18164 KB |
Output is correct |
40 |
Correct |
4897 ms |
17168 KB |
Output is correct |
41 |
Correct |
4482 ms |
19232 KB |
Output is correct |
42 |
Correct |
4525 ms |
19484 KB |
Output is correct |