Submission #1215310

#TimeUsernameProblemLanguageResultExecution timeMemory
1215310NeltRadio Towers (IOI22_towers)C++20
0 / 100
4083 ms6668 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; ll a[N], n, lef[N], rig[N]; void init(int N, vector<int> H) { n = N; for (ll i = 1; i <= n; i++) a[i] = H[i - 1]; } int max_towers(int l, int r, int d) { l++, r++; vector<pair<ll, ll>> st; for (ll i = l; i <= r; 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] = l - 1; else lef[i] = (pos - 1)->second; st.push_back(make_pair(a[i], i)); } while (!st.empty()) st.pop_back(); for (ll i = r; i >= l; 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] = r + 1; else rig[i] = (pos - 1)->second; st.push_back(make_pair(a[i], i)); } vector<pair<ll, ll>> segs; for (ll i = l; i <= r; i++) segs.push_back(make_pair(rig[i], lef[i])); // sort(segs.begin(), segs.end()); ll cur = -1, ans = 0; for (auto [r, l] : segs) if (l >= cur) cur = r, ans++; 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...