Submission #1211605

#TimeUsernameProblemLanguageResultExecution timeMemory
1211605LithaniumDancing Elephants (IOI11_elephants)C++20
26 / 100
33 ms2372 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> // #include "camera.h" using namespace std; constexpr int K = 130; constexpr int T = 12; int curr = 0; int loc[70005]; int old[70005]; set<pair<int, int>> batch, all, extra; bool seen[70005]; int lift[T][70005]; int N, L; inline void calc() { vector<pair<int, int>> order(N); for (int i = 0; i < N; i ++) order[i] = {loc[i], i}; sort(order.begin(), order.end()); for (int i = 0; i < N; i ++) { old[i] = loc[i]; int t = lower_bound(order.begin(), order.end(), make_pair(order[i].first + L + 1, -1)) - order.begin(); lift[0][order[i].second] = N; if (t < N) lift[0][order[i].second] = order[t].second; } lift[0][N] = N; for (int i = 1; i < 11; i ++) { for (int j = 0; j <= N; j ++) { lift[i][j] = lift[i-1][lift[i-1][j]]; } } for (auto [a, b]:batch) seen[b] = 0; batch.clear(); extra.clear(); extra.insert({2e9+5, N}); batch.insert({2e9+5, N}); } void init(int n, int l, int X[]) { N = n, L = l; for (int i = 0; i < N; i ++) { loc[i] = X[i]; old[i] = X[i]; lift[0][i] = lower_bound(X, X+N, loc[i] + L + 1) - X; all.insert({X[i], i}); } old[N] = 2e9+5; loc[N] = 2e9+5; all.insert({2e9+5, N}); lift[0][N] = N; for (int i = 1; i < T; i ++) { for (int j = 0; j <= N; j ++) { lift[i][j] = lift[i-1][lift[i-1][j]]; } } extra.insert({2e9+5, N}); batch.insert({2e9+5, N}); } int update(int i, int y /*, int debug = 0*/) { all.erase({loc[i], i}); all.insert({y, i}); if (seen[i]) { batch.erase({loc[i], i}); batch.insert({y, i}); } else { seen[i] = 1; extra.insert({old[i], i}); batch.insert({y, i}); } loc[i] = y; if (batch.size() == K) calc(); auto it = batch.begin(), it2 = extra.begin(); int upto = all.begin()->second, ans = 0; while (upto < N) { // see how far it can be placed if (upto != it->second) { // there are some disruptor events for (int i = T-1; i >= 0; i --) if (old[lift[i][upto]] < min(it2->first, it->first)) { upto = lift[i][upto]; ans += (1 << i); } } if (upto == N) { return ans; } // forced placements do { ans ++; upto = all.lower_bound(make_pair(loc[upto] + L + 1, -1))->second; while (it->first < loc[upto]) it = next(it); while (it2->first < loc[upto]) it2 = next(it2); } while (upto < N and it->first <= loc[upto] + L + 1); } 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...