Submission #836949

#TimeUsernameProblemLanguageResultExecution timeMemory
836949Abrar_Al_SamitRadio Towers (IOI22_towers)C++17
23 / 100
4099 ms7504 KiB
#include "towers.h" #include <bits/stdc++.h> using namespace std; //subtask 2 & 3 const int nax = 100005; int n; bool l_maxima[nax]; int l[nax], r[nax]; int h[nax]; int pmax[nax], nmax[nax]; void init(int N, vector<int> H) { n = N; for(int i=0; i<n; ++i) h[i] = H[i]; } bool is[nax]; int max_towers(int L, int R, int D) { vector<int>H; for(int i=L; i<=R; ++i) { H.push_back(h[i]); } n = R-L+1; int mn = H[0]; for(int i=1; i<n-1; ++i) { if(H[i]>H[i-1] && H[i]>H[i+1]) { l_maxima[i] = 1; l[i] = H[i] - mn; mn = 2e9; } else { mn = min(mn, H[i]); } } int p = -1; for(int i=1; i<n; ++i) if(l_maxima[i]) { pmax[i] = p; p = i; } p = n; for(int i=n-1; i>0; --i) if(l_maxima[i]) { nmax[i] = p; p = i; } mn = H[n-1]; for(int i=n-2; i>0; --i) { if(l_maxima[i]) { r[i] = H[i] - mn; mn = 2e9; } else { mn = min(mn, H[i]); } } int ret = 1; set<pair<int,int>>s; for(int i=1; i<n; ++i) if(l_maxima[i]) { s.insert({H[i], i}); is[i] = 1; } while(!s.empty()) { auto [x, i] = *s.begin(); s.erase(s.begin()); is[i] = 0; if(min(l[i], r[i])>=D) { ++ret; continue; } int lmin = H[i] - l[i], rmin = H[i] - r[i]; if(pmax[i]!=-1 && is[pmax[i]]) { r[pmax[i]] = max(r[pmax[i]], H[pmax[i]] - rmin); nmax[pmax[i]] = nmax[i]; } if(nmax[i]!=n && is[nmax[i]]) { l[nmax[i]] = max(l[nmax[i]], H[nmax[i]] - lmin); pmax[nmax[i]] = pmax[i]; } } return ret; }
#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...