제출 #542457

#제출 시각아이디문제언어결과실행 시간메모리
542457tabr코끼리 (Dancing Elephants) (IOI11_elephants)C++17
97 / 100
9014 ms6708 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]; 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_ * (n <= 1000 ? 1 : 2)); for (int i = 0; i < n; i++) { x[i] = x_[i]; } for (int i = 0; i < B; i++) { e[i].reserve(n / B + 10); } 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 x[i] < x[j]; }); for (int i = 0; i < (int) e[id].size(); i++) { pos[e[id][i]] = id; } 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 x[i] < x[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]].erase(find(e[pos[i]].begin(), e[pos[i]].end(), i)); build_one(pos[i]); // 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...