Submission #832527

#TimeUsernameProblemLanguageResultExecution timeMemory
832527NothingXDRadio Towers (IOI22_towers)C++17
23 / 100
4097 ms10540 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; void debug_out(){cerr << endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 1e5 + 10; const int lg = 20; int n, h[maxn], mx[lg][maxn], l[maxn], r[maxn], f[2][maxn]; void add(int *f, int idx, int x){ for (; idx <= n; idx += idx & -idx) f[idx] += x; } void add(int *f, int l, int r, int x){ add(f, l, x); add(f, r+1, -x); } int get(int *f, int idx){ int res = 0; for (; idx; idx -= idx & -idx) res += f[idx]; return res; } int get(int *f, int l, int r){ if (r < l) return 0; return get(f, r) - get(f, l-1); } int getmax(int l, int r){ r++; int x = 31 - __builtin_clz(r-l); return max(mx[x][l], mx[x][r-(1 << x)]); } void init(int N, std::vector<int> H) { n = N; for (int i = 0; i < n; i++){ h[i] = H[i]; mx[0][i] = h[i]; } for (int i = 1; i < lg; i++){ for (int j = 0; j + (1 << i) <= n; j++){ mx[i][j] = max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]); } } } int max_towers(int L, int R, int D) { memset(l, 0, sizeof l); memset(r, 0, sizeof r); memset(f, 0, sizeof f); for (int i = L; i <= R; i++){ int lo = L, hi = i; while(lo + 1 < hi){ int mid = (lo + hi) >> 1; if (getmax(mid, i-1) - D >= h[i]) lo = mid; else hi = mid; } l[i] = lo; } vector<pii> val; for (int i = L; i <= R; i++){ int lo = i, hi = R; while(lo + 1 < hi){ int mid = (lo + hi) >> 1; if (getmax(i+1, mid) - D >= h[i]) hi = mid; else lo = mid; } r[i] = hi; val.push_back({h[i], i}); } //debug(1); sort(all(val)); int ans = 0; for (auto [x, y]: val){ if (get(f[0], y+1)) continue; if (get(f[1], l[y]+1, r[y]+1)) continue; ans++; add(f[0], l[y]+1, r[y]+1, 1); add(f[1], y+1, 1); } 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...