Submission #101837

#TimeUsernameProblemLanguageResultExecution timeMemory
101837alexpetrescuDancing Elephants (IOI11_elephants)C++14
97 / 100
9065 ms7204 KiB
#include "elephants.h" #include <vector> #include <algorithm> #define MAXN 150000 #define MAXR 110 #define LOGR 6 #define MAXK 1400 #define LOGK 11 bool seen; int n, l, k, r, mareleCnt; std::vector < int > v[MAXR]; int u[MAXN], p[MAXN], poz[MAXN]; struct myc { int x, y; } dp[MAXN]; inline void calc(std::vector < int > &t) { int j = t.size() - 1; for (int i = t.size() - 1; i >= 0; i--) { if (u[t[i]] + l >= u[t.back()]) dp[t[i]] = {1, u[t[i]] + l}; else { while (j - 1 > i && u[t[j - 1]] > u[t[i]] + l) j--; dp[t[i]] = {1 + dp[t[j]].x, dp[t[j]].y}; } } } void init(int N, int L, int X[]) { if (seen == 0) { n = N; l = L; k = MAXK; seen = 1; for (int i = 0; i < n; i++) p[i] = i; for (int i = 0; i < n; i++) u[i] = X[i]; } r = 1 + (n - 1) / k; for (int i = 0; i < r; i++) { v[i].resize(std::min(n, (i + 1) * k) - i * k); for (int j = i * k; j < n && j < (i + 1) * k; j++) v[i][j - i * k] = p[j], poz[p[j]] = i; } for (int i = r - 1; i >= 0; i--) calc(v[i]); } inline void myInit() { int aici[1] = {0}; int j = 0; for (int i = 0; i < r; i++) for (auto &x : v[i]) p[j++] = x; init(0, 0, aici); } inline void scoate(int p) { int i = 0; while (v[poz[p]][i] != p) i++; while (i + 1 < (int)v[poz[p]].size()) { v[poz[p]][i] = v[poz[p]][i + 1]; i++; } v[poz[p]].pop_back(); } inline void baga(int p) { int i = 0; while (i < (int)v[poz[p]].size() && u[v[poz[p]][i]] < u[p]) i++; v[poz[p]].push_back(0); for (int j = v[poz[p]].size() - 1; j > i; j--) v[poz[p]][j] = v[poz[p]][j - 1]; v[poz[p]][i] = p; } int update(int i, int y) { int e = 0, f = poz[i]; for (int pas = 1 << LOGR; pas; pas >>= 1) if (e + pas < r && u[v[e + pas][0]] <= y) e += pas; scoate(i); poz[i] = e; u[i] = y; baga(i); mareleCnt++; if (mareleCnt % k == 0) myInit(); else if (f == e) calc(v[e]); else if (((int)v[f].size() == 0 && f != r - 1) || (int)v[e].size() == 2 * r) myInit(); else if (e < f) { if ((int)v[f].size() == 0) r--; else calc(v[f]); calc(v[e]); } else { calc(v[e]); calc(v[f]); } int val = -1, ans = 0; for (int i = 0; i < r; i++) { if (val < u[v[i].back()]) { int rez = -1; for (int pas = 1 << LOGK; pas; pas >>= 1) if (rez + pas < (int)v[i].size() && u[v[i][rez + pas]] <= val) rez += pas; rez++; ans += dp[v[i][rez]].x; val = dp[v[i][rez]].y; } } return ans; }
#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...