Submission #763476

#TimeUsernameProblemLanguageResultExecution timeMemory
763476amunduzbaevRadio Towers (IOI22_towers)C++17
0 / 100
523 ms282556 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, tot; struct STMx{ vector<int> tree; int N; STMx(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); } int first(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(tree[x] < v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(tree[x << 1] >= v) return first(l, r, v, lx, m, x << 1); else return first(l, r, v, m + 1, rx, x << 1 | 1); } int m = (lx + rx) >> 1; int res = first(l, r, v, lx, m, x << 1); if(res == -1) res = first(l, r, v, m + 1, rx, x << 1 | 1); } int first(int l, int r, int v){ return first(l, r, v, 0, N, 1); } int last(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(tree[x] < v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(tree[x << 1 | 1] >= v) return last(l, r, v, m + 1, rx, x << 1 | 1); else return last(l, r, v, lx, m, x << 1); } int m = (lx + rx) >> 1; int res = last(l, r, v, m + 1, rx, x << 1 | 1); if(res == -1) res = last(l, r, v, lx, m, x << 1); return res; } int last(int l, int r, int v){ return last(l, r, v, 0, N, 1); } }Max(N); struct ST{ vector<int> Max, Min, t01, t10; int N; ST(int N): N(N){ Max.resize(N << 2); Min.resize(N << 2); t01.resize(N << 2); t10.resize(N << 2); } void set(int i, int v, int lx, int rx, int x){ if(lx == rx){ t01[x] = t10[x] = 0; Max[x] = Min[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); t01[x] = max({t01[x << 1], t01[x << 1 | 1], Max[x << 1 | 1] - Min[x << 1]}); t10[x] = max({t10[x << 1], t10[x << 1 | 1], Max[x << 1] - Min[x << 1 | 1]}); Max[x] = max(Max[x << 1], Max[x << 1 | 1]); Min[x] = min(Min[x << 1], Min[x << 1 | 1]); } void set(int i, int v){ set(i, v, 0, N, 1); } int mn, mx; int get01(int l, int r, int d, int lx, int rx, int x){ if(lx > r || rx < l){ return -1; } if(lx >= l && rx <= r){ if(t01[x] < d && Max[x] - mn < d){ mn = min(mn, Min[x]); return -1; } if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Max[x << 1] - mn >= d || t01[x << 1] >= d){ return get01(l, r, d, lx, m, x << 1); } else { mn = min(mn, Min[x << 1]); return get01(l, r, d, m + 1, rx, x << 1 | 1); } } int m = (lx + rx) >> 1; int res = get01(l, r, d, lx, m, x << 1); if(res == -1) res = get01(l, r, d, m + 1, rx, x << 1 | 1); return res; } int get01(int l, int r, int d){ mn = inf; return get01(l, r, d, 0, N, 1); } int get10(int l, int r, int d, int lx, int rx, int x){ if(lx > r || rx < l){ return -1; } if(lx >= l && rx <= r){ if(t10[x] < d && Max[x] - mn < d){ mn = min(mn, Min[x]); return -1; } if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Max[x << 1 | 1] - mn >= d || t10[x << 1 | 1] >= d){ return get10(l, r, d, m + 1, rx, x << 1 | 1); } else { mn = min(mn, Min[x << 1 | 1]); return get10(l, r, d, lx, m, x << 1); } } int m = (lx + rx) >> 1; int res = get10(l, r, d, m + 1, rx, x << 1 | 1); if(res == -1) res = get10(l, r, d, lx, m, x << 1); return res; } int get10(int l, int r, int d){ mn = inf; return get10(l, r, d, 0, N, 1); } }tree(N); struct sqrtDec{ vector<int> a; vector<vector<int>> cnt; int N, B; sqrtDec(int N, int B): N(N), B(B){ a.resize(N); cnt.resize(B, vector<int>(N + 1)); } void set(int i, int v){ a[i] = v; cnt[i / B][v]++; } void build(){ for(int i=0;i<B;i++){ for(int j=N-1;j>=0;j--){ cnt[i][j] += cnt[i][j + 1]; } } } int get(int l, int r, int v){ int l_ = l / B, r_ = r / B; int res = 0; for(int j=l_+1;j<r_;j++){ res += cnt[j][v]; } if(l_ == r_){ for(int i=l;i<=r;i++){ res += (a[i] >= v); } } else { for(int i=l;i<(l_+1)*B;i++){ res += (a[i] >= v); } for(int i=r_*N;i<=r;i++){ res += (a[i] >= v); } } return res; } int first(int l, int r, int v){ int l_ = l / B, r_ = r / B; for(int i=l;i<min(r + 1, (l_ + 1) * B);i++){ if(a[i] >= v) return i; } for(int j=l_ + 1;j<r_;j++){ if(cnt[j][v]){ for(int k=j*B;k<(j+1)*B;k++){ if(a[k] >= v) return k; } } } for(int i=r_*B;i<=r;i++){ if(a[i] >= v) return i; } assert(false); } int last(int l, int r, int v){ int l_ = l / B, r_ = r / B; for(int i=r;i>=max(l, r_*B);i--){ if(a[i] >= v) return i; } for(int j=r_-1;j>l_;j--){ if(cnt[j][v]){ for(int k=(j+1)*B-1;k>=j*B;k--){ if(a[k] >= v) return k; } } } for(int i=(l_ + 1) * B - 1;i>=l;i--){ if(a[i] >= v) return i; } assert(false); } }block(N, 320); 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){ 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]); } 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) tot.push_back(x[0]); tot.erase(unique(tot.begin(), tot.end()), tot.end()); vector<int> v(n); for(auto [d, i] : res){ v[i] = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1; } for(int i=0;i<n;i++){ tree.set(i, a[i]); block.set(i, v[i]); } block.build(); } int max_towers(int l, int r, int d) { int D = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1; 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; int res = block.get(l, r, D); if(!res){ int l_ = tree.get01(l, r, d), r_ = tree.get10(l, r, d); if(~l_ && ~r_ && l_ <= r_){ return 2; } return 1; } int l_ = block.first(l, r, D), r_ = block.last(l, r, D); l_ = Max.last(l, l_, a[l_] + d); r_ = Max.first(r_, r, a[r_] + d); //~ cout<<l_<<" "<<r_<<"\n"; if(~l_ && ~tree.get01(l, l_, d)){ res++; } if(~r_ && ~tree.get10(r_, r, d)){ res++; } return res; }

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:361:6: warning: unused variable 'n' [-Wunused-variable]
  361 |  int n = a.size();
      |      ^
towers.cpp: In member function 'int STMx::first(int, int, int, int, int, int)':
towers.cpp:72:2: warning: control reaches end of non-void function [-Wreturn-type]
   72 |  }
      |  ^
#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...