Submission #1079469

#TimeUsernameProblemLanguageResultExecution timeMemory
1079469LittleOrangeRadio Towers (IOI22_towers)C++17
14 / 100
701 ms3536 KiB
#include "towers.h" #include <vector> #include<bits/stdc++.h> using namespace std; using ll = int; const ll big = 1e9+10; ll n; vector<ll> h; //ll mx; vector<ll> ps; struct obj{ ll v,c; bool operator<(const obj &o) const{ return v<o.v; } bool operator>(const obj &o) const{ return v>o.v; } }; void init(int N, std::vector<int> H) { n = N; h = H; //for(ll i = 0;i<n;i++) if((i==0||(h[i-1]<h[i]))&&(i==n-1||h[i]>h[i+1])) mx = i; //for(ll i = 1;i<n-1;i++){ // if (h[i-1]<h[i]&&h[i]>h[i+1]){ // ps.push_back(i); // } //} //for(auto [u,v] : ps) cerr << "[" << u << "," << v << "]" << " ";cerr << "\n"; } bool ps_inited = false; void init_ps(ll d){ ps_inited = true; vector<ll> l(n,0),r(n,0); { vector<pair<ll,ll>> v; v.push_back({h[0],h[0]}); for(ll i = 1;i<n;i++){ ll mi = h[i]; while(v.size()&&v.back().first<h[i]){ mi = min(mi,v.back().second); v.pop_back(); } if (mi<=h[i]-d) l[i] = 1; v.push_back({h[i],mi}); } } { vector<pair<ll,ll>> v; v.push_back({h[n-1],h[n-1]}); for(ll i = n-2;i>=0;i--){ ll mi = h[i]; while(v.size()&&v.back().first<h[i]){ mi = min(mi,v.back().second); v.pop_back(); } if (mi<=h[i]-d) r[i] = 1; v.push_back({h[i],mi}); } } for(ll i = 0;i<n;i++) if(l[i]&&r[i]) ps.push_back(i); } int max_towers(int L, int R, int D) { if(!ps_inited) init_ps(D); ll l = L, r = R, d = D; ll ans = 1; auto it0 = lower_bound(ps.begin(),ps.end(),r); ll rf = it0-ps.begin(); auto it1 = lower_bound(ps.begin(),ps.end(),l+1); ll lf = it1-ps.begin(); //cerr << lf << " " << rf << "\n"; return max(0,rf-lf)+1; /*vector<obj> a,b; a.push_back({0,0}); b.push_back({big,0}); for(ll i = l;i<=r;i++){ ll cur = 0; auto it = lower_bound(b.begin(),b.end(),obj({h[i]-1,0}),greater<obj>()); --it; cur = (*it).c; ans = max(ans,cur+1); obj oa = {h[i],cur+1}; if (a.size()<=oa.c) a.push_back(oa); else a[oa.c] = min(a[oa.c],oa); auto it0 = lower_bound(a.begin(),a.end(),obj({h[i]-d+1,0})); --it0; obj ob = {h[i]-d,(*it0).c}; if (b.size()<=ob.c) b.push_back(ob); else b[ob.c] = max(b[ob.c],ob); ans = max(ans,cur+1); //cerr << "a:";for(auto [u,v] : a) cerr << "(" << u <<"," << v << ") ";cerr << "\n"; //cerr << "b:";for(auto [u,v] : b) cerr << "(" << u <<"," << v << ") ";cerr << "\n"; }*/ return ans; }

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:68:20: warning: unused variable 'd' [-Wunused-variable]
   68 |   ll l = L, r = R, d = 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...