Submission #1215329

#TimeUsernameProblemLanguageResultExecution timeMemory
1215329NeltRadio Towers (IOI22_towers)C++20
0 / 100
239 ms17968 KiB
#include "towers.h" #include <bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; const ll N = 1e5 + 5, inf = 2e18, lg = 17; ll a[N], n, lef[N], rig[N], up[lg][N]; ll suf[N]; ll mn[N]; bool flg = 0; void init(int N, vector<int> H) { n = N; for (ll i = 1; i <= n; i++) a[i] = H[i - 1]; } void precomp(ll d) { vector<pair<ll, ll>> st; for (ll i = 1; i <= n; i++) { while (!st.empty() and a[i] > st.back().first) st.pop_back(); auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater()); if (pos == st.begin()) lef[i] = 0; else lef[i] = (pos - 1)->second; st.push_back(make_pair(a[i], i)); } while (!st.empty()) st.pop_back(); for (ll i = n; i >= 1; i--) { while (!st.empty() and a[i] > st.back().first) st.pop_back(); auto pos = lower_bound(st.begin(), st.end(), make_pair(a[i] + d - 1, inf), greater()); if (pos == st.begin()) rig[i] = n + 1; else rig[i] = (pos - 1)->second; st.push_back(make_pair(a[i], i)); } for (ll i = 1; i <= n; i++) mn[i] = suf[i] = n + 2; for (ll i = 1; i <= n; i++) mn[lef[i]] = min(mn[lef[i]], rig[i]), suf[i] = rig[i]; for (ll i = 0; i < lg; i++) up[i][n + 1] = up[i][n + 2] = n + 2; for (ll i = n - 1; i >= 1; i--) suf[i] = min(suf[i], suf[i + 1]), mn[i] = min(mn[i + 1], mn[i]); for (ll i = n; i >= 1; i--) { up[0][i] = mn[i]; for (ll j = 1; j < lg; j++) up[j][i] = up[j - 1][up[j - 1][i]]; } } int max_towers(int l, int r, int d) { l++, r++; if (!flg) precomp(d), flg = 1; if (suf[l] > r) return 1; l = suf[l]; ll ans = 1; if (up[0][l] > r + 1) return 1; for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][l] <= r + 1) ans += 1 << bit, l = up[bit][l]; 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...