제출 #426360

#제출 시각아이디문제언어결과실행 시간메모리
426360JeanBombeur코끼리 (Dancing Elephants) (IOI11_elephants)C++17
97 / 100
5728 ms13564 KiB
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> #include "elephants.h" using namespace std; const int INFINI = (1000 * 1000 * 1000 + 1); const int MAX_ELEPHANTS = (150 * 1000); const int SQRT = (400); int Positions[MAX_ELEPHANTS]; vector <int> Elephants[SQRT]; vector <pair <int, int>> Answer[SQRT]; int nbElephants, tailleIntervalle; void UpdateBucket(int bucket) { int sz = Elephants[bucket].size(); int droite = sz; for (int i = droite - 1; i >= 0; i --) { while (Elephants[bucket][droite - 1] > Elephants[bucket][i] + tailleIntervalle) droite --; if (droite == sz) Answer[bucket][i] = {1, Elephants[bucket][i] + tailleIntervalle}; else Answer[bucket][i] = {1 + Answer[bucket][droite].first, Answer[bucket][droite].second}; } return; } void Insert(int bucket, int val) { vector <int> nv; for (int a : Elephants[bucket]) { if (a >= val) { nv.push_back(val); val = INFINI; } nv.push_back(a); } if (val < INFINI) nv.push_back(val); Elephants[bucket] = nv; Answer[bucket].push_back({0, 0}); UpdateBucket(bucket); return; } void Remove(int bucket, int val) { vector <int> nv; for (int a : Elephants[bucket]) { if (a == val) val = -1; else nv.push_back(a); } Elephants[bucket] = nv; UpdateBucket(bucket); return; } int FindNext(int bucket, int val) { int ans = -1; int sz = Elephants[bucket].size(); for (int i = (1 << 8); i > 0; i /= 2) { if (ans + i < sz && Elephants[bucket][ans + i] <= val) ans += i; } return ans + 1; } int FindAnswer() { int ans = 0; int curBucket = 0; int curId = 0; while (Elephants[curBucket].size() > 0) { ans += Answer[curBucket][curId].first; int saut = Answer[curBucket][curId].second; curId = FindNext(++ curBucket, saut); while (curId != 0 && curId == (int)Elephants[curBucket].size()) curId = FindNext(++ curBucket, saut); } return ans; } void ResetBuckets() { vector <int> AllPos; int curBucket = 0; while (Elephants[curBucket].size() > 0) { for (int a : Elephants[curBucket]) AllPos.push_back(a); curBucket ++; } for (int i = 0; i < curBucket; i ++) { Elephants[i].clear(); Answer[i].clear(); } curBucket = 0; for (int i = 0; i < nbElephants; i ++) { if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2) curBucket ++; Elephants[curBucket].push_back(AllPos[i]); Answer[curBucket].push_back({0, 0}); } for (int i = 0; i <= curBucket; i ++) { UpdateBucket(i); } return; } void init(int N, int L, int X[]) { nbElephants = N; tailleIntervalle = L; for (int i = 0; i < nbElephants; i ++) { Positions[i] = X[i]; } sort(X, X + nbElephants); int curBucket = 0; for (int i = 0; i < nbElephants; i ++) { if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2) curBucket ++; Elephants[curBucket].push_back(X[i]); Answer[curBucket].push_back({0, 0}); } for (int i = 0; i <= curBucket; i ++) { UpdateBucket(i); } return; } int update(int id, int nouvPos) { int prev = Positions[id]; Positions[id] = nouvPos; int curBucket = 0; bool reset = false; while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < prev) curBucket ++; if (Elephants[curBucket].size() == 0) curBucket --; Remove(curBucket, prev); if (Elephants[curBucket].size() == 1) reset = true; curBucket = 0; while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < nouvPos) curBucket ++; if (Elephants[curBucket].size() == 0) curBucket --; Insert(curBucket, nouvPos); if (Elephants[curBucket].size() >= 2 * SQRT) reset = true; if (reset) ResetBuckets(); return FindAnswer(); }
#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...