Submission #781992

#TimeUsernameProblemLanguageResultExecution timeMemory
781992FEDIKUSRadio Towers (IOI22_towers)C++17
0 / 100
4158 ms2097152 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; using mim = pair<pair<int,int>,int>; const int maxn=1e5+10; const int logg=18; int n; int h[maxn]; mim sparse[maxn][logg]; mim comb(mim &a,mim &b){ mim ret=a; ret.first=max(ret.first,b.first); ret.second=min(ret.second,b.second); return ret; } void init(int _n, vector<int> _h) { n=_n; for(int i=0;i<n;i++) h[i]=_h[i]; for(int i=0;i<logg;i++){ for(int j=0;j<n;j++){ if(i==0) sparse[i][j]={{h[j],j},h[j]}; else if(j-(1<<(i-1))>=0) sparse[i][j]=comb(sparse[i-1][j],sparse[i-1][j-(1<<(i-1))]); else sparse[i][j]=sparse[i-1][j]; } } } mim qry(int l,int r){ mim ret={{h[l],l},h[l]}; for(int i=logg-1;i>=0;i--){ if(r-(1<<i)+1>=l){ ret=comb(ret,sparse[i][r]); r-=(1<<i); } } return ret; } int resi(int l,int r,int d,int naj=1e9+10){ if(r<l) return 0; auto temp=qry(l,r); pair<int,int> maxi=temp.first; int klk=temp.second<=naj; return max(resi(l,maxi.second-1,d,maxi.first-d)+resi(maxi.second+1,r,d,maxi.first-d),int(klk>0)); } int max_towers(int l, int r, int d) { return resi(l,r,d); }
#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...