Submission #626067

#TimeUsernameProblemLanguageResultExecution timeMemory
626067nigusRadio Towers (IOI22_towers)C++17
17 / 100
1090 ms45600 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); V = (l->V); trav(y, r->V){ V.push_back(y); } sort(all(V)); reverse(all(V)); } else{ 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 = max(l->get_ab(L, R), r->get_ab(L, R)); int x = l->get_min(L,R); int y = r->get_max(L,R); return max(res,y-x); } int get_ba(int L, int R){ if (R <= lo || hi <= L) return 0; if (L <= lo && hi <= R) return ba; int res = max(l->get_ba(L, R), r->get_ba(L, R)); int x = r->get_min(L,R); int y = l->get_max(L,R); return max(res,y-x); } 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(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); } int max_towers(int L, int R, int D){ R++; return (ST->geq(L,R,D))+1; } /* int main() { int N; N = 7; vi H = {1,4,2,9,3,6,5}; init(N,H); cout << max_towers(0, 7, 1) << "\n"; cout << max_towers(0, 7, 2) << "\n"; cout << max_towers(0, 7, 3) << "\n"; cout << max_towers(0, 7, 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...