Submission #58482

#TimeUsernameProblemLanguageResultExecution timeMemory
58482ngkan146Dancing Elephants (IOI11_elephants)C++11
100 / 100
7621 ms13124 KiB
#include "elephants.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; const int maxBlockLen = 700; int n, length; int numBlock; int block[400][2000], blockSz[2000]; int bFind(int id,int val){ for(int i=0;;i++) if (block[id][i] == val) return i; } void bInsert(int id,int pos,int val){ for(int i=blockSz[id];i>pos;i--) block[id][i] = block[id][i-1]; block[id][pos] = val; blockSz[id] ++; } void bErase(int id,int pos){ blockSz[id] --; for(int i=pos;i<blockSz[id];i++) block[id][i] = block[id][i+1]; } ii startFromThis[400][2000]; // [blockId][position] = {last position, how many jumps} int elephantPos[150005], elephantBLock[150005]; void reBuild(int blockId){ //~ sort(block[blockId].begin(), block[blockId].end()); // assuming sorted int nextPos = blockSz[blockId]; for(int i = blockSz[blockId]-1;i >= 0; i--){ while(nextPos > 0 && block[blockId][nextPos-1] > block[blockId][i] + length) -- nextPos; if (nextPos == blockSz[blockId]) startFromThis[blockId][i] = {block[blockId][i], 0}; else startFromThis[blockId][i] = startFromThis[blockId][nextPos], startFromThis[blockId][i].second ++; } } int lst[150005]; void reBuildFull(){ for(int i=1;i<=numBlock;i++) blockSz[i] = 0; numBlock = 1; for(int i=0;i<n;i++) lst[i] = i; sort(lst, lst+n, [&](int x,int y){ return elephantPos[x] < elephantPos[y]; }); for(int i=0;i<n;i++){ if (blockSz[numBlock] == maxBlockLen) ++ numBlock; block[numBlock][blockSz[numBlock]++] = elephantPos[lst[i]]; elephantBLock[lst[i]] = numBlock; } for(int i=1;i<=numBlock;i++){ reBuild(i); } } int cntUpdTimes; int update(int elephantId, int newPos){ if (++cntUpdTimes % 650 == 0) reBuildFull(); //~ cout << "turn " << cntUpdTimes << endl; bErase(elephantBLock[elephantId], bFind(elephantBLock[elephantId], elephantPos[elephantId])); reBuild(elephantBLock[elephantId]); elephantPos[elephantId] = newPos; for(int i=1;i<=numBlock;i++){ if (i == numBlock || newPos <= block[i][blockSz[i]-1]){ // block[i].empty() only occur when i = numBlock elephantBLock[elephantId] = i; for(int j=0;j<=blockSz[i];j++){ if (j == blockSz[i] || newPos <= block[i][j]){ bInsert(i, j, newPos); break; } } reBuild(i); break; } } // find res int res = 0; int last = (int)-(1e9+5); for(int i=1;i<=numBlock;i++){ int startHere = upper_bound(block[i], block[i]+blockSz[i], last + length) - block[i]; if (startHere == blockSz[i]) continue; res += startFromThis[i][startHere].second + 1; last = startFromThis[i][startHere].first; } return res; } void init(int N, int L, int X[]){ n = N; length = L; for(int i=0;i<N;i++){ elephantPos[i] = X[i]; } reBuildFull(); }
#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...