Submission #833234

#TimeUsernameProblemLanguageResultExecution timeMemory
833234pavementRadio Towers (IOI22_towers)C++17
0 / 100
835 ms38564 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; #define eb emplace_back #define mp make_pair using ii = pair<int, int>; int N; bool is_init; vector<int> H, cl, cr; vector<vector<int> > anc; vector<ii> segs; void init(int N, vector<int> H) { ::N = N; ::H = H; cl = vector<int>(N, -1); cr = vector<int>(N, N); anc = vector<vector<int> >(20, vector<int>(N, -1)); } struct node { node *left, *right; int S, E; ii val; node(int _s, int _e) : S(_s), E(_e), val(-1, -1) { if (S == E) { return; } int M = (S + E) / 2; left = new node(S, M); right = new node(M + 1, E); } void upd(int p, ii v) { val = max(val, v); if (S == E) { return; } int M = (S + E) / 2; if (p <= M) { left->upd(p, v); } else { right->upd(p, v); } } ii qry(int r) { if (r < S) { return mp(-1, -1); } if (E <= r) { return val; } return max(left->qry(r), right->qry(r)); } } *root; int max_towers(int L, int R, int D) { if (!is_init) { vector<ii> vec; for (int i = 0; i < N; i++) { { int lo = 0, hi = (int)vec.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (vec[mid].first <= H[i] - D) { cl[i] = vec[mid].second; lo = mid + 1; } else { hi = mid - 1; } } } while (!vec.empty() && vec.back().first >= H[i]) { vec.pop_back(); } vec.eb(H[i], i); } vec.clear(); for (int i = N - 1; i >= 0; i--) { { int lo = 0, hi = (int)vec.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (vec[mid].first <= H[i] - D) { cr[i] = vec[mid].second; lo = mid + 1; } else { hi = mid - 1; } } } while (!vec.empty() && vec.back().first >= H[i]) { vec.pop_back(); } vec.eb(H[i], i); } for (int i = 0; i < N; i++) { if (cl[i] != -1 && cr[i] != N) { segs.eb(cr[i], cl[i]); } } sort(segs.begin(), segs.end()); root = new node(0, N - 1); for (int i = 0; i < (int)segs.size(); i++) { int to = root->qry(segs[i].second).second; anc[0][i] = to; for (int k = 1; k < 20; k++) { if (anc[k - 1][i] == -1) { break; } anc[k][i] = anc[k - 1][anc[k - 1][i]]; } root->upd(segs[i].first, mp(segs[i].second, i)); } is_init = 1; } int st = root->qry(R).second; if (segs[st].second < L) { return 1; } int ans = 2; for (int k = 19; k >= 0; k--) { if (anc[k][st] != -1 && segs[anc[k][st]].second >= L) { st = anc[k][st]; ans += (1 << k); } } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...