Submission #626111

#TimeUsernameProblemLanguageResultExecution timeMemory
626111nigusRadio Towers (IOI22_towers)C++17
0 / 100
4059 ms32600 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; const ll big = 1000000007; const int MAXN = 100001; int n; vi H2; struct Segtree { Segtree *l = 0, *r = 0; int lo, hi, ma = -big, mi = big, ab = 0, ba = 0; vi V = {}; Segtree(vi& v, int lo, int hi) : lo(lo), hi(hi) { if (lo + 1 < hi) { int mid = lo + (hi - lo)/2; l = new Segtree(v, lo, mid); r = new Segtree(v, mid, hi); ma = max(l->ma, r->ma); mi = min(l->mi, r->mi); ab = max(l->ab, r->ab); ab = max(ab, (r->ma) - (l->mi)); ba = max(l->ba, r->ba); ba = max(ba, (l->ma) - (r->mi)); } else{ ma = v[lo]; mi = v[lo]; } } void setup(vi &v){ if(lo + 1 < hi){ l->setup(v); r->setup(v); int x = 0; int y = 0; while(x < sz(l->V) || y < sz(r->V)){ if(y == sz(r->V) || (x < sz(l->V) && l->V[x] >= r->V[y])){ V.push_back(l->V[x]); x++; } else{ V.push_back(r->V[y]); y++; } } } else{ if(v[lo] > 0){V = {v[lo]};} } } int get_max(int L, int R) { if (R <= lo || hi <= L) return -big; if (L <= lo && hi <= R) return ma; return max(l->get_max(L, R), r->get_max(L, R)); } int get_min(int L, int R) { if (R <= lo || hi <= L) return big; if (L <= lo && hi <= R) return mi; return min(l->get_min(L, R), r->get_min(L, R)); } int get_ab(int L, int R){ if (R <= lo || hi <= L) return 0; if (L <= lo && hi <= R) return ab; int res = (l->get_ab(L, R)); if(res < r->ab){ res = max(res, r->get_ab(L, R)); } if(res < (r->ma) - (l->mi)){ int x = l->get_min(L,R); int y = r->get_max(L,R); res = max(res, y-x); } return res; } int get_ba(int L, int R){ if (R <= lo || hi <= L) return 0; if (L <= lo && hi <= R) return ba; int res = l->get_ba(L, R); if(res < r->ba){ res = max(res, r->get_ba(L, R)); } if(res < (l->ma) - (r->mi)){ int x = r->get_min(L, R); int y = l->get_max(L, R); res = max(res, y-x); } return res; } int geq(int L, int R, int D){ if (R <= lo || hi <= L) return 0; if (L <= lo && hi <= R){ int lo = 0; int hi = sz(V); if(sz(V) == 0)return 0; if(V[0] < D)return 0; while(lo < hi-1){ int mid = (lo + hi) / 2; if(V[mid] < D){ hi = mid; } else{ lo = mid; } } return hi; } return (l->geq(L, R, D)) + (r->geq(L, R, D)); } }; Segtree *ST; map<int,int> HI; vi delta; vi ind; void get_ct(int L, int R){ if(L >= R)return; if(L == R-1){ delta[L] = 0; return; } int i = HI[ST->get_max(L, R)]; int x = ST->get_min(L,i); int y = ST->get_min(i+1,R); delta[i] = H2[i]-max(x, y); delta[i] = max(delta[i], 0); get_ct(L, i); get_ct(i+1,R); } bool comp(int i, int j){ return delta[i] > delta[j]; } void init(int N, vi H){ n = N; rep(c1,0,n){ H2.push_back(H[c1]); HI[H[c1]] = c1; ind.push_back(c1); delta.push_back(0); } ST = new Segtree(H2, 0, n); get_ct(0, n); sort(all(ind), comp); ST->setup(delta); } unordered_map<ll,int> M; int first_ab(ll L, ll R, ll D){ ll h = 2*(L*big + D); if(M.find(h) != M.end())return M[h]; int lo = L; int hi = R; while(lo < hi-1){ int mid = (lo+hi)/2; if(ST->get_ab(L, mid+1) < D){ lo = mid; } else{ hi = mid; } } M[h] = hi; return hi; } int last_ba(ll L, ll R, ll D){ ll h = 2*(R*big + D) + 1; if(M.find(h) != M.end())return M[h]; int lo = L; int hi = R; while(lo < hi-1){ int mid = (lo+hi)/2; if(ST->get_ba(mid, R) >= D){ lo = mid; } else{ hi = mid; } } M[h] = lo; return lo; } int max_towers(int L, int R, int D){ R++; if(ST->get_ab(L, R) < D || ST->get_ba(L, R) < D)return 1; int i = first_ab(L, R, D); int j = last_ba(L, R, D)+1; return 2112; return (ST->geq(i,j,D))+1; } /* int main() { int N; N = 7; vi H = {1,4,2,9,3,6,5}; init(N,H); cout << max_towers(0, 6, 1) << "\n"; cout << max_towers(0, 6, 2) << "\n"; cout << max_towers(0, 6, 3) << "\n"; cout << max_towers(0, 6, 10) << "\n"; return 0; } */
#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...