Submission #1039792

#TimeUsernameProblemLanguageResultExecution timeMemory
103979242kangarooRadio Towers (IOI22_towers)C++17
17 / 100
1131 ms5580 KiB
#include "towers.h" #include "bits/stdc++.h" using namespace std; struct SegTeRan { vector<int> a; int get(int l, int r, int i, int lq, int rq) { if (r <= lq || rq <= l) return 0; if (lq <= l && r <= rq) return a[i]; int m = (l + r)/2; return max(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq, rq)); } int set(int l, int r, int i, int k, int v) { if (k < l || r <= k) return a[i]; if (l + 1 == r) return a[i] = v; int m = (l + r)/2; return a[i] = max(set(l, m, 2*i + 1, k, v), set(m, r, 2*i + 2, k, v)); } }; struct SegTeMa{ vector<int> a; int build(int l, int r, int i, vector<int>& in) { if (l + 1 == r) return a[i] = in[l]; int m = (l + r)/2; return a[i] = max(build(l, m, 2*i + 1, in), build(m, r, 2*i + 2, in)); } int firLe(int l, int r, int i, int k, int hi) { if (l > k) return -1; if (a[i] < hi) return -1; if (l + 1 == r) return l; int m = (l + r)/2; int reR = firLe(m, r, 2*i + 2, k, hi); if (reR != -1) return reR; return firLe(l, m, 2*i + 1, k, hi); } int firRi(int l, int r, int i, int k, int hi) { if (r <= k) return -1; if (a[i] < hi) return -1; if (l + 1 == r) return l; int m = (l + r)/2; int reR = firRi(l, m, 2*i + 1, k, hi); if (reR != -1) return reR; return firRi(m, r, 2*i + 2, k, hi); } }; vector<int> ch; void init(int N, std::vector<int> H) { SegTeMa maSe{vector<int>(4*N)}; SegTeRan raSe{vector<int>(4*N, 0)}; maSe.build(0, N, 0, H); vector<int> o(N); std::iota(o.begin(), o.end(),0); std::sort(o.begin(), o.end(), [&](int l, int r){return H[l] < H[r];}); for (int i = 0; i < N; ++i) { int l = 0, r = 1e9 + 1; while (l + 1 < r) { int m = l + (r - l)/2; int leB = maSe.firLe(0, N, 0, o[i], H[o[i]] + m), reB = maSe.firRi(0, N, 0, o[i], H[o[i]] + m); if (leB == -1) leB = 0; if (reB == -1) reB = N; if (raSe.get(0, N, 0, leB, reB) < m) l = m; else r = m; } raSe.set(0, N, 0, o[i], l); ch.push_back(l); } std::sort(ch.begin(), ch.end()); } int max_towers(int L, int R, int D) { return std::upper_bound(ch.rbegin(), ch.rend(),D, greater<>()) - ch.rbegin(); }
#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...