Submission #542452

#TimeUsernameProblemLanguageResultExecution timeMemory
542452tabrDancing Elephants (IOI11_elephants)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif const int MAX_N = 150015; const int MAX_B = 810; int B; int n; int l; int upd_cnt; int x[MAX_N]; pair<int, int> pos[MAX_N]; int jump_cnt[MAX_N]; int jump_pos[MAX_N]; vector<int> e[MAX_B]; int order[MAX_N]; void init(int n_, int l_, int x_[]) { n = n_; l = l_; B = (int) sqrt(n_ * 2); for (int i = 0; i < n; i++) { x[i] = x_[i]; } iota(order, order + n, 0); } void build_one(int id) { assert(!e[id].empty()); sort(e[id].begin(), e[id].end(), [&](int i, int j) { return make_pair(x[i], i) < make_pair(x[j], j); }); for (int i = 0; i < (int) e[id].size(); i++) { pos[e[id][i]] = make_pair(id, i); } for (int i = (int) e[id].size() - 1, j = (int) e[id].size(); i >= 0; i--) { while (j > 0 && x[e[id][j - 1]] > x[e[id][i]] + l) { j--; } if (j == (int) e[id].size()) { jump_cnt[e[id][i]] = 1; jump_pos[e[id][i]] = x[e[id][i]] + l + 1; } else { jump_cnt[e[id][i]] = jump_cnt[e[id][j]] + 1; jump_pos[e[id][i]] = jump_pos[e[id][j]]; } } } void build() { sort(order, order + n, [&](int i, int j) { return make_pair(x[i], i) < make_pair(x[j], j); }); for (int i = 0; i < B; i++) { e[i].clear(); for (int j = n * i / B; j < n * (i + 1) / B; j++) { e[i].emplace_back(order[j]); } build_one(i); } } int update(int i, int y) { if (n == 1) { return 1; } if (upd_cnt == 0) { build(); } upd_cnt++; if (upd_cnt == n / B - 1) { upd_cnt = 0; } // remove x[i] e[pos[i].first].erase(e[pos[i].first].begin() + pos[i].second); build_one(pos[i].first); // add x[i] x[i] = y; for (int id = 0; id < B; id++) { if (id == B - 1 || x[e[id + 1][0]] > y) { e[id].emplace_back(i); build_one(id); break; } } // answer int ans = 0; int now = 0; for (int id = 0; id < B; id++) { x[150001] = now; auto iter = lower_bound(e[id].begin(), e[id].end(), 150001, [&](int j, int k) { return x[j] < x[k]; }); if (iter == e[id].end()) { continue; } ans += jump_cnt[*iter]; now = jump_pos[*iter]; } return ans; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); int n_ = 4; int l_ = 10; int x_[10]; x_[0] = 10; x_[1] = 15; x_[2] = 17; x_[3] = 20; init(n_, l_, x_); debug(update(2, 16)); // 1 debug(update(1, 25)); // 2 debug(update(3, 35)); // 2 debug(update(0, 38)); // 2 debug(update(2, 0)); // 3 return 0; } #endif
#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...