Submission #816871

#TimeUsernameProblemLanguageResultExecution timeMemory
816871AlphaBruhRadio Towers (IOI22_towers)C++17
0 / 100
4059 ms4828 KiB
#include "towers.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define inf 2e9 vector<int>hs; struct bd{ int h=-1, id=0; bool operator>(bd a){ return h > a.h; } }; bd tree[350000]; bd bdmx(bd a, bd b){ if(a.h>b.h) return a; return b; } int n,d; void build(int l, int r,int id){ if(l==r){ tree[id].h=hs[l]; tree[id].id=l; return; } int m = (l+r)>>1; build(l,m,id*2); build(m+1,r,id*2+1); tree[id] = bdmx(tree[id*2],tree[id*2+1]); return; } bd get_max(int l, int r, int s, int e, int id){ if(s <= l && r <=e){ return tree[id]; } int m = (l+r)>>1; bd mx; if(s<=m){ mx = bdmx(mx,get_max(l,m,s,e,id*2)); } if(m+1<=e){ mx = bdmx(mx,get_max(m+1,r,s,e,id*2+1)); } return mx; } vector<int>mxid(200005,-1); int rent_max(int l, int r, int lmh,int from,int lor){ //printf("%d %d %d\n",l,r,lmh); if(l>r) return 0; if(l==r){ if(lmh >= hs[l]){ return 1; } return 0; } bd mxb; if(lor==-1 || mxid[from*2+lor]==-1){ mxb = get_max(0,n-1,l,r,1); mxid[from*2+lor]=mxb.id; } else{ mxb.id = mxid[from*2+lor]; mxb.h = hs[mxb.id]; } int lm = rent_max(l,mxb.id-1,mxb.h-d,mxb.id,0); int rm = rent_max(mxb.id+1,r,mxb.h-d,mxb.id,1); int be = lm+rm, nbe; nbe = max(lm,rm); return max(max(be,nbe),1); } void init(int N, std::vector<int> H) { n=N; hs.assign(H.begin(),H.end()); build(0,N-1,1); } int max_towers(int L, int R, int D) { d=D; return rent_max(L,R,inf,n,-1); }
#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...