제출 #151337

#제출 시각아이디문제언어결과실행 시간메모리
151337GioChkhaidze코끼리 (Dancing Elephants) (IOI11_elephants)C++14
100 / 100
5468 ms15208 KiB
#include <bits/stdc++.h> #include "elephants.h" using namespace std; const int Na=150006; const int Nq=400; int n,m,Ms,l,Updcnt,A[Na]; int Lmax[Nq][3*Nq]; int Llen[Nq][3*Nq]; vector < int > v[Nq]; void process_block(int x) { int r=v[x].size()-1,rmax=v[x][v[x].size()-1]; for (int i=v[x].size()-1; i>=0; i--) { int pos=v[x][i]; if (pos+l>=v[x][r]) { Lmax[x][i]=pos+l; Llen[x][i]=1; } else { while (0<r && pos+l<v[x][r-1]) r--; Lmax[x][i]=Lmax[x][r]; Llen[x][i]=Llen[x][r]+1; } } } int get_ans() { int res=0,cur_block=0; while (cur_block<Ms && !v[cur_block].size()) cur_block++; int pos=v[cur_block][0],idx=0; while (cur_block<Ms) { int Lmx=Lmax[cur_block][idx]; res+=Llen[cur_block][idx]; while (cur_block<Ms) { cur_block++; if (!v[cur_block].size()) continue; if (Lmx<v[cur_block][v[cur_block].size()-1]) { int l=0,r=v[cur_block].size()-1,mid; while (l<=r) { mid=(l+r)/2; if (Lmx<v[cur_block][mid]) { idx=mid; r=mid-1; } else l=mid+1; } break; } } } return res; } void restart() { vector < int > h; for (int i=0; i<Ms; i++) { for (int j=0; j<v[i].size(); j++) h.push_back(v[i][j]); v[i].clear(); } for (int i=0; i<h.size(); i++) v[i/m].push_back(h[i]); for (int i=0; i<Ms; i++) process_block(i); } void del(int x) { int cur_block=-1; while (cur_block<Ms) { cur_block++; if (!v[cur_block].size()) continue; if (v[cur_block][v[cur_block].size()-1]<x) continue; for (int j=0; j<v[cur_block].size(); j++) if (v[cur_block][j]==x) { v[cur_block].erase(v[cur_block].begin()+j); break; } break; } process_block(cur_block); } void ins(int x) { int cur_block=-1; while (cur_block<Ms) { cur_block++; if (!v[cur_block].size()) continue; if (v[cur_block][v[cur_block].size()-1]<=x) continue; for (int j=0; j<v[cur_block].size(); j++) if (x<v[cur_block][j]) { v[cur_block].insert(v[cur_block].begin()+j,x); break; } break; } if (cur_block==Ms) { cur_block--; v[cur_block].push_back(x); } process_block(cur_block); } int update(int id, int nv) { del(A[id]); A[id]=nv; ins(A[id]); Updcnt++; if (!(Updcnt%m)) restart(); return get_ans(); } void init(int nn, int ll, int xs[]) { n=nn,l=ll; m=sqrt(n); m+=(m*m!=n); Ms=(n+m-1)/m; for (int i=0; i<n; i++) { A[i]=xs[i]; v[i/m].push_back(A[i]); } for (int i=0; i<Ms; i++) process_block(i); return; }

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

elephants.cpp: In function 'void process_block(int)':
elephants.cpp:17:22: warning: unused variable 'rmax' [-Wunused-variable]
  int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
                      ^~~~
elephants.cpp: In function 'int get_ans()':
elephants.cpp:40:6: warning: unused variable 'pos' [-Wunused-variable]
  int pos=v[cur_block][0],idx=0;
      ^~~
elephants.cpp: In function 'void restart()':
elephants.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[i].size(); j++) 
                 ~^~~~~~~~~~~~
elephants.cpp:71:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j=0; j<v[i].size(); j++) 
   ^~~
elephants.cpp:73:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    v[i].clear();
    ^
elephants.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<h.size(); i++) 
                ~^~~~~~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~
#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...