제출 #558820

#제출 시각아이디문제언어결과실행 시간메모리
558820mosiashvililuka코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
5256 ms20860 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...