Submission #635275

#TimeUsernameProblemLanguageResultExecution timeMemory
635275tutisRadio Towers (IOI22_towers)C++17
0 / 100
4086 ms88536 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; vector<int>H; struct ST { int l, r; ST *left, *right; int mn; ST() {} vector<pair<int, int>>V; vector<pair<int, int>>W; ST(int l, int r): l(l), r(r) { if (l < r) { left = new ST(l, (l + r) / 2); right = new ST((l + r) / 2 + 1, r); mn = min(left->mn, right->mn); } else { left = right = NULL; mn = H[l]; } for (int i = l; i <= r; i++) { if (W.empty() || H[i] > W.back().first) W.push_back({H[i], i}); } int mm = 2e9; for (int i = l + 1; i <= r; i++) { mm = min(mm, H[i - 1]); if (V.empty() || H[i] - mm > V.back().first) V.push_back({H[i] - mm, i}); } } 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)); } pair<int, int> get1(int L, int D, int mnl = 2e9) { if (L <= l) { int rr = -1; auto it = lower_bound(V.begin(), V.end(), make_pair(D, -1)); if (it != V.end()) rr = it->second; //W-mn>=D //W>=D+mn it = lower_bound(W.begin(), W.end(), make_pair(D + mn, -1)); if (it != W.end()) { int r1 = it->second; if (r == -1) rr = r1; else rr = min(r, r1); } return {rr, mn}; } if (r < L) return { -1, 2e9}; pair<int, int> i = left->get1(L, D, mnl); pair<int, int> j = right->get1(L, D, min(i.second, mnl)); j.second = min(j.second, i.second); if (i.first != -1) j.first = i.first; return j; } } medis; vector<vector<pair<int, int>>>Fl, Fr; int N; vector<int>prv; vector<int>nxt; void init(int N_, vector<int> H_) { N = N_; H = H_; prv = vector<int>(N, -1); nxt = vector<int>(N, N + 1); { vector<int>A; for (int i = 0; i < N; i++) { while (!A.empty() && H[A.back()] <= H[i]) A.pop_back(); if (!A.empty()) prv[i] = A.back(); A.push_back(i); } A.clear(); for (int i = N - 1; i >= 0; i--) { while (!A.empty() && H[A.back()] <= H[i]) A.pop_back(); if (!A.empty()) nxt[i] = A.back(); A.push_back(i); } } 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); 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 = medis.get1(L, D).first; int yy = -1; 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...