Submission #763507

#TimeUsernameProblemLanguageResultExecution timeMemory
763507amunduzbaevRadio Towers (IOI22_towers)C++17
0 / 100
613 ms26552 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; const int B = 320; //~ 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); //~ int cnt[B][N]; struct sqrtDec{ int a[N]; sqrtDec(){ memset(a, 0, sizeof a); //~ memset(cnt, 0, sizeof cnt); } 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 - 2;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_*B;i<=r;i++){ //~ res += (a[i] >= v); //~ } //~ } //~ return res; int res = 0; for(int i=l;i<=r;i++){ if(a[i] >= v){ res++; } } 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; //~ } //~ assert(false); //~ } //~ } //~ for(int i=max(l, r_ * B);i<=r;i++){ //~ if(a[i] >= v) return i; //~ } //~ assert(false); for(int i=l;i<=r;i++){ if(a[i] >= v) return i; } assert(false); return 0; } 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; //~ } //~ assert(false); //~ } //~ } //~ for(int i=(l_ + 1) * B - 1;i>=l;i--){ //~ if(a[i] >= v) return i; //~ } //~ assert(false); for(int i=r;i>=l;i--){ if(a[i] >= v) return i; } assert(false); return 0; } }block; 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]); assert(v[i] <= N); 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(); //~ 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:383:6: warning: unused variable 'n' [-Wunused-variable]
  383 |  int n = a.size();
      |      ^
towers.cpp: In member function 'int STMx::first(int, int, int, int, int, int)':
towers.cpp:73:2: warning: control reaches end of non-void function [-Wreturn-type]
   73 |  }
      |  ^
#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...