Submission #763403

#TimeUsernameProblemLanguageResultExecution timeMemory
763403amunduzbaevRadio Towers (IOI22_towers)C++17
17 / 100
884 ms12612 KiB
#include "towers.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "stub.cpp" #endif #define ar array typedef int64_t ll; //~ #define int ll const int inf = 1e9 + 7; const int N = 1e5 + 5; //~ int first, mount; //~ vector<int> a, l, r, res; vector<ar<int, 2>> res; vector<int> a; struct ST{ vector<int> tree; int N; ST(int N): N(N){ tree.resize(N << 2); } void set(int i, int v, int lx, int rx, int x){ if(lx == rx){ tree[x] = v; return; } int m = (lx + rx) >> 1; if(i <= m) set(i, v, lx, m, x << 1); else set(i, v, m + 1, rx, x << 1 | 1); tree[x] = max(tree[x << 1], tree[x << 1 | 1]); } void set(int i, int v){ set(i, v, 0, N, 1); } int get(int l, int r, int lx, int rx, int x){ if(lx > r || rx < l){ return -(N << 2); } if(lx >= l && rx <= r){ return tree[x]; } int m = (lx + rx) >> 1; return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1)); } int get(int l, int r){ return get(l, r, 0, N, 1); } }Max(N), Min(N); void init(int n, vector<int> h) { a = h; vector<int> pos; for(int i=0;i<n;i++){ Max.set(i, a[i]); if((!i || a[i] < a[i - 1]) && (i + 1 == n || a[i] < a[i + 1])){ pos.push_back(i); } } set<int> ss; multiset<ar<int, 2>> dif; for(int i=0;i<(int)pos.size();i++){ if(i){ //~ a[pos[i]] a[pos[i - 1]] int mx = Max.get(pos[i - 1], pos[i]); dif.insert({mx - a[pos[i - 1]], pos[i - 1]}); dif.insert({mx - a[pos[i]], pos[i]}); } ss.insert(pos[i]); } //~ for(auto x : ss){ //~ cout<<x<<" "; //~ } //~ cout<<"\n"; while(!dif.empty()){ auto [d, i] = *dif.begin(); res.push_back({d, i}); //~ cout<<i<<" "<<d<<"\n"; auto it = ss.lower_bound(i); auto R = it; R++; if(it == ss.begin() || R == ss.end()){ if(it == ss.begin()){ int mx = Max.get(*it, *R); dif.erase(dif.find({mx - a[*it], *it})); dif.erase(dif.find({mx - a[*R], *R})); } else { auto L = it; L--; int mx = Max.get(*L, *it); dif.erase(dif.find({mx - a[*it], *it})); dif.erase(dif.find({mx - a[*L], *L})); } ss.erase(it); continue; } auto L = it; --L; int mx = Max.get(*L, *it); dif.erase(dif.find({mx - a[*it], *it})); dif.erase(dif.find({mx - a[*L], *L})); mx = Max.get(*it, *R); dif.erase(dif.find({mx - a[*it], *it})); dif.erase(dif.find({mx - a[*R], *R})); mx = Max.get(*L, *R); dif.insert({mx - a[*L], *L}); dif.insert({mx - a[*R], *R}); ss.erase(it); } res.push_back({inf, *ss.begin()}); //~ for(auto x : res) cout<<x[0]<<" "; //~ cout<<"\n"; for(int i=1;i<(int)res.size();i++){ assert(res[i - 1][0] <= res[i][0]); } } int max_towers(int l_, int r_, int d) { int n = a.size(); //~ assert(l_ == 0 && r_ == n - 1); int j = lower_bound(res.begin(), res.end(), (ar<int, 2>){d, 0}) - res.begin(); return (int)res.size() - j; }

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:138:6: warning: unused variable 'n' [-Wunused-variable]
  138 |  int n = a.size();
      |      ^
#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...