Submission #1022999

#TimeUsernameProblemLanguageResultExecution timeMemory
1022999mansurRadio Towers (IOI22_towers)C++17
27 / 100
4035 ms32560 KiB
#include "towers.h" #include<bits/stdc++.h> using namespace std; #define rall(s) s.rbegin(), s.rend() #define all(s) s.begin(), s.end() #define sz(s) (int)s.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; vector<int> h; int n, k, ok = 1; const int inf = 1e9, N1 = 3e7; pii t[N1]; void bld(int u = 1, int tl = 0, int tr = n - 1) { if (tl == tr) { t[u] = {tl, tl}; return; } int m = (tl + tr) / 2; bld(u * 2, tl, m); bld(u * 2 + 1, m + 1, tr); t[u] = t[u * 2 + 1]; if (h[t[u * 2].f] > h[t[u].f]) t[u].f = t[u * 2].f; if (h[t[u * 2].s] < h[t[u].s]) t[u].s = t[u * 2].s; } pii get(int l, int r, int u = 1, int tl = 0, int tr = n - 1) { if (tl > r || tr < l) return {-1, -1}; if (tl >= l && tr <= r) return t[u]; int m = (tl + tr) / 2; auto [x1, x2] = get(l, r, u * 2, tl, m); auto [y1, y2] = get(l, r, u * 2 + 1, m + 1, tr); if (x1 == -1) return {y1, y2}; if (y1 == -1) return {x1, x2}; if (h[y1] > h[x1]) x1 = y1; if (h[y2] < h[x2]) x2 = y2; return {x1, x2}; } int t2[N1], vl[N1], vr[N1], cur = 1; void upd(int l, int r, int u = 1, int tl = 1, int tr = inf) { if (tl > r || tr < l || r < l) return; if (tl >= l && tr <= r) { t2[u]++; return; } int m = (tl + 0ll + tr) / 2; if (!vl[u]) vl[u] = ++cur; if (!vr[u]) vr[u] = ++cur; upd(l, r, vl[u], tl, m); upd(l, r, vr[u], m + 1, tr); } int gt(int p, int u = 1, int tl = 1, int tr = inf) { if (tl == tr) return t2[u]; int m = (tl + + 0ll + tr) / 2; if (p <= m) { if (vl[u]) return gt(p, vl[u], tl, m) + t2[u]; return t2[u]; } if (vr[u]) return gt(p, vr[u], m + 1, tr) + t2[u]; return t2[u]; } void calc(int l, int r, int mx) { if (r < l) return; if (l == r) { upd(1, mx - h[l]); return; } auto [pos, ps] = get(l, r); if (pos == l) calc(l + 1, r, mx); else if (pos == r) calc(l, r - 1, mx); else { upd(h[pos] - h[ps] + 1, mx - h[ps]); calc(l, pos - 1, h[pos]); calc(pos + 1, r, h[pos]); } } void init(int N, vector<int> H) { n = N, h = H; k = n - 1; for (int i = 1; i < n; i++) { if (h[i] < h[i - 1]) { k = i - 1; break; } } for (int i = 1; i < k; i++) { if (h[i - 1] > h[i]) ok = 0; } for (int i = k + 1; i < n; i++) { if (h[i - 1] < h[i]) ok = 0; } bld(); calc(0, n - 1, 2 * inf); } int f(int l, int r, int d, int mx) { if (r < l) return 0; if (l == r) return (h[l] <= mx); auto [pos, ps] = get(l, r); if (h[ps] > mx) return 0; if (pos == l) return f(l + 1, r, d, mx); if (pos == r) return f(l, r - 1, d, mx); return max(1, f(l, pos - 1, d, min(mx, h[pos] - d)) + f(pos + 1, r, d, min(mx, h[pos] - d))); } int max_towers(int l, int r, int d) { if (ok) { if (k == -1) return 1; if (k <= l || r <= k) return 1; if (h[l] > h[k] - d || h[r] > h[k] - d) return 1; return 2; } if (l == 0 && r == n - 1) { //return gt(d); } return f(l, r, d, inf); }
#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...