Submission #1078861

#TimeUsernameProblemLanguageResultExecution timeMemory
1078861LittleOrangeRadio Towers (IOI22_towers)C++17
0 / 100
4077 ms1916 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; 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; } int max_towers(int L, int R, int D) { ll l = L, r = R, d = D; ll ans = 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:40:17: warning: comparison of integer expressions of different signedness: 'std::vector<obj>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   40 |     if (a.size()<=oa.c) a.push_back(oa);
      |         ~~~~~~~~^~~~~~
towers.cpp:45:17: warning: comparison of integer expressions of different signedness: 'std::vector<obj>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   45 |     if (b.size()<=ob.c) b.push_back(ob);
      |         ~~~~~~~~^~~~~~
#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...