Submission #94049

#TimeUsernameProblemLanguageResultExecution timeMemory
94049fjzzq2002Dancing Elephants (IOI11_elephants)C++14
97 / 100
9025 ms21900 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; #define SZ 305555 int n; //B? #define pb push_back typedef pair<int,int> pii; #define fi first #define se second int B=150,G=0; vector<int> bl[SZ]; vector<int> seq; set<pii> ns; int be[SZ],x[SZ],W,blk[SZ]; int ts[SZ]; int* getseq() { int tn=0; for(auto t:seq) for(int j=0;j<bl[t].size();++j) ts[tn++]=bl[t][j]; return ts; } #define j1 ju1 int j1[SZ]; pii js[SZ]; inline void reset_block(vector<int>&v_) { int j=0,vn=v_.size(),*v=v_.data(); for(int i=0;i<vn;++i) { while(j<vn&&x[v[j]]<=x[v[i]]+W) ++j; if(j==vn) j1[v[i]]=-1; else j1[v[i]]=v[j]; } for(int i=int(vn)-1;i>=0;--i) if(j1[v[i]]==-1) js[v[i]].fi=v[i],js[v[i]].se=0; else js[v[i]].fi=js[j1[v[i]]].fi, js[v[i]].se=js[j1[v[i]]].se+1; } inline void rebuild(int*v) { int u=int(n)/B; if(!u) ++u; for(int i=1;i<=G;++i) bl[i].clear(); seq.clear(); G=0; vector<int> p; p.reserve(u); for(int i=0;i<n;++i) { p.pb(v[i]); if(p.size()>=u||i==n-1) { bl[++G]=p,reset_block(p); for(auto t:p) blk[t]=G; seq.pb(G),p.clear(); p.reserve(u); } } } inline int ask() { int s=ns.begin()->se,cn=0; while(1) { if(js[s].se) cn+=js[s].se,s=js[s].fi; auto u=ns.lower_bound(pii(x[s]+W+1,0)); ++cn; if(u==ns.end()) break; s=u->se; } return cn; } int cnt=0; void init(int N, int L_, int X[]) { n=N; W=L_; for(int i=0;i<n;++i) x[i]=X[i]; vector<int> v; for(int i=0;i<n;++i) v.pb(i),ns.insert(pii(x[i],i)); rebuild(v.data()); } int update(int t,int y) { ns.erase(pii(x[t],t)); { int i=blk[t]; vector<int>&B=bl[i]; for(int j=0;;++j) if(B[j]==t) { for(int k=j;k+1<B.size();++k) B[k]=B[k+1]; B.pop_back(); break; } if(B.size()) reset_block(B); else { for(int j=0;;++j) if(seq[j]==i) { for(int k=j;k+1<seq.size();++k) seq[k]=seq[k+1]; seq.pop_back(); break; } } } x[t]=y; ns.insert(pii(x[t],t)); for(int i=0;i<int(seq.size());++i) if(x[t]<=x[bl[seq[i]].back()]||i+1==int(seq.size())) { while(x[bl[seq[i]].back()]<=x[t] &&i+1!=int(seq.size())&&rand()%3) ++i; static int us[SZ]; int un=0; vector<int> &s=bl[seq[i]]; bool c=0; for(int j=0;j<s.size();++j) { if(x[s[j]]>x[t]) {if(!c) us[un++]=t; c=1;} us[un++]=s[j]; } if(!c) us[un++]=t; s.pb(0); for(int i=0;i<un;++i) s[i]=us[i]; reset_block(s); blk[t]=seq[i]; break; } ++cnt; if(cnt%(B*3)==0) rebuild(getseq()); return ask(); }

Compilation message (stderr)

elephants.cpp: In function 'int* getseq()':
elephants.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<bl[t].size();++j)
               ~^~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild(int*)':
elephants.cpp:53:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p.size()>=u||i==n-1)
      ~~~~~~~~^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j;k+1<B.size();++k)
                 ~~~^~~~~~~~~
elephants.cpp:103:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j;k+1<seq.size();++k)
                  ~~~^~~~~~~~~~~
elephants.cpp:117:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<s.size();++j)
                ~^~~~~~~~~
elephants.cpp:123:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(!c) us[un++]=t; s.pb(0);
    ^~
elephants.cpp:123:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(!c) us[un++]=t; s.pb(0);
                       ^
#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...