Submission #1022892

#TimeUsernameProblemLanguageResultExecution timeMemory
1022892IssaRadio Towers (IOI22_towers)C++17
41 / 100
4098 ms268008 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int maxn = 1e5 + 100; int n, k; int a[maxn]; int t[maxn]; int dp[maxn]; vector<pii> g[maxn]; int l[maxn]; int r[maxn]; int pref[maxn]; void upd(int i, int x){ for(; i <= n; i |= (i + 1)) t[i] = max(t[i], x); } int get(int i){ int res = 0; for(; i > 0; i = (i & (i + 1)) - 1) res = max(res, t[i]); return res; } void init(int N, std::vector<int> H){ n = N; for(int i = 1; i <= n; i++){ a[i] = H[i-1]; } k = 1; while(k < n && a[k+1] > a[k]) k++; for(int i = k + 1; i <= n; i++){ if(a[i-1] < a[i]) k = 0; } for(int i = 1; i <= n; i++){ pref[i] = pref[i-1]; if(a[i] < min(a[i+1], a[i-1])) pref[i]++; } } int max_towers(int L, int R, int D){ if(L == R) return 1; L++; R++; if(k){ if(L < k && k < R && max(a[L], a[R]) + D <= a[k]) return 2; return 1; } if(D == 1){ int ans = pref[R-1] - pref[L]; if(a[L] < a[L+1]) ans++; if(a[R] < a[R-1]) ans++; return ans; } for(int i = 1; i <= n; i++){ t[i] = 0; g[i].clear(); } vector<int> v; for(int i = L; i <= R; i++){ while(v.size() && a[v.back()] <= a[i]) v.pop_back(); v.push_back(i); l[i] = L - 1; for(int tl = 0, tr = v.size() - 1; tl <= tr;){ int mid = (tl + tr) >> 1; if(a[v[mid]] - D < a[i]) tr = mid - 1; else tl = mid + 1, l[i] = v[mid]; } } v.clear(); for(int i = R; i >= L; i--){ while(v.size() && a[v.back()] <= a[i]) v.pop_back(); v.push_back(i); r[i] = R + 1; for(int tl = 0, tr = v.size() - 1; tl <= tr;){ int mid = (tl + tr) >> 1; if(a[v[mid]] - D < a[i]) tr = mid - 1; else tl = mid + 1, r[i] = v[mid]; } } int ans = 0; for(int i = L; i <= R; i++){ for(auto [p, x]: g[i]){ upd(p, x); } dp[i] = get(l[i]) + 1; g[r[i]].push_back({i, dp[i]}); ans = max(ans, dp[i]); } 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...