Submission #635259

#TimeUsernameProblemLanguageResultExecution timeMemory
635259tutisRadio Towers (IOI22_towers)C++17
23 / 100
4043 ms68288 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; struct ST { int l, r; ST *left, *right; int mn; ST() {} ST(int l, int r, const vector<int>& h): l(l), r(r) { if (l < r) { left = new ST(l, (l + r) / 2, h); right = new ST((l + r) / 2 + 1, r, h); mn = min(left->mn, right->mn); } else { left = right = NULL; mn = h[l]; } } int get(int x, int y) { if (x <= l && r <= y) return mn; if (r < x || y < l) return 2e9; return min(left->get(x, y), right->get(x, y)); } } medis; vector<vector<pair<int, int>>>Fl, Fr; int N; vector<int>H; void init(int N_, vector<int> H_) { N = N_; H = H_; vector<int> p(N); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](int a, int b) {return H[a] > H[b];}); set<int>X; medis = ST(0, N - 1, H); auto get = [&](int l, int r) { if (l + 1 >= r) return -1; int h = medis.get(l + 1, r - 1); return max(0, min(H[l] - h, H[r] - h)); }; map<int, vector<pair<int, int>>>L; map<int, vector<pair<int, int>>>R; auto add = [&](int l, int r, int d, int w) { R[d].push_back({r, w}); L[d].push_back({l, w}); }; for (int i : p) { int r = -1, l = -1; auto it = X.lower_bound(i); if (it != X.end()) { r = *it; } if (it != X.begin()) { it--; l = *it; } X.insert(i); if (l == -1 || r == -1) { if (r != -1 && i + 1 < r) add(i, r, get(i, r), 1); if (l != -1 && l + 1 < i) add(l, i, get(l, i), 1); } else { int d = get(l, r); int d1 = get(i, r); int d2 = get(l, i); if (d1 >= 0 || d2 >= 0) { add(i, r, d1, 1); add(l, i, d2, 1); assert(max(d1, d2) <= d); add(l, r, max(d1, d2), -1); } } } Fl = vector<vector<pair<int, int>>>(N); Fr = vector<vector<pair<int, int>>>(N); for (const auto &dd : L) { int d = dd.first; for (pair<int, int>lw : dd.second) for (int i = lw.first; i < N; i |= i + 1) { if (!Fl[i].empty() && Fl[i].back().first == d) Fl[i].back().second += lw.second; else Fl[i].push_back({d, lw.second}); } } for (const auto &dd : R) { int d = dd.first; for (pair<int, int>rw : dd.second) for (int i = rw.first; i < N; i |= i + 1) { if (!Fr[i].empty() && Fr[i].back().first == d) Fr[i].back().second += rw.second; else Fr[i].push_back({d, rw.second}); } } for (int i = 0; i < N; i++) { for (int j = 1; j < (int)Fl[i].size(); j++) Fl[i][j].second += Fl[i][j - 1].second; for (int j = 1; j < (int)Fr[i].size(); j++) Fr[i][j].second += Fr[i][j - 1].second; } } int get(int l, int r, int d) { int ret = 0; int i = r; while (i >= 0) { if (!Fr[i].empty()) { auto it = lower_bound(Fr[i].begin(), Fr[i].end(), make_pair(d, (int) - 1e9)); ret += Fr[i].back().second; if (it != Fr[i].begin()) { it--; ret -= it->second; } } i = (i & (i + 1)) - 1; } i = l - 1; while (i >= 0) { if (!Fl[i].empty()) { auto it = lower_bound(Fl[i].begin(), Fl[i].end(), make_pair(d, (int) - 1e9)); ret -= Fl[i].back().second; if (it != Fl[i].begin()) { it--; ret += it->second; } } i = (i & (i + 1)) - 1; } return ret; } int max_towers(int L, int R, int D) { int xx = -1; int yy = -1; for (int x = L + 1; x <= R; x++) { if (medis.get(L, x - 1) + D <= H[x]) { xx = x; break; } } for (int y = R - 1; y >= L; y--) { if (medis.get(y + 1, R) + D <= H[y]) { yy = y; break; } } if (xx != -1 && yy != -1 && xx <= yy) return 2 + get(xx, yy, D); return 1; }
#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...