제출 #832440

#제출 시각아이디문제언어결과실행 시간메모리
832440ymm송신탑 (IOI22_towers)C++17
100 / 100
1098 ms49384 KiB
#include "towers.h" #include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x) typedef long long ll; using namespace std; const int inf = 1e9+10; const int N = 100'010; template<class T, class CMP> struct rmq { static int constexpr lg = 18; CMP cmp; typedef pair<T,int> el; vector<el> vec[lg]; int sz; el mn(const el &x, const el &y) { return cmp(x.first, y.first)? x: y; } void init(const vector<T> &a) { sz = a.size(); vec[0].resize(sz); Loop (i,0,sz) vec[0][i] = {a[i], i}; Loop (j,0,lg-1) { if ((2<<j) > sz) break; vec[j+1].resize(sz-(2<<j)+1); for (int i = 0; i + (2<<j) <= sz; ++i) vec[j+1][i] = mn(vec[j][i], vec[j][i+(1<<j)]); } } el get(int l, int r) { int k = __lg(r-l); return mn(vec[k][l], vec[k][r-(1<<k)]); } }; rmq<int, less<int>> rmq_mn; rmq<int, greater<int>> rmq_mx; namespace seg { vector<int> t[4*N]; int sz; void init(const vector<int> &vec, int i, int b, int e) { if (e-b == 1) { t[i] = {vec[b]}; return; } init(vec, 2*i+1, b, (b+e)/2); init(vec, 2*i+2, (b+e)/2, e); t[i].resize(t[2*i+1].size() + t[2*i+2].size()); merge(t[2*i+1].begin(), t[2*i+1].end(), t[2*i+2].begin(), t[2*i+2].end(), t[i].begin()); } void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); } int get(int l, int r, int d, int i, int b, int e) { if (l <= b && e <= r) return t[i].end() - lower_bound(t[i].begin(), t[i].end(), d); if (r <= b || e <= l) return 0; return get(l, r, d, 2*i+1, b, (b+e)/2) + get(l, r, d, 2*i+2, (b+e)/2, e); } int get(int l, int r, int d) { return get(l, r, d, 0, 0, sz); } int lrmost(int l, int r, int d, bool dir, int i, int b, int e) { if (r <= b || e <= l || t[i].back() < d) return -1; if (e-b == 1) return b; int ans = -1; ans = lrmost(l, r, d, dir, 2*i+1+ dir, dir? (b+e)/2: b, dir? e: (b+e)/2); if (ans != -1) return ans; ans = lrmost(l, r, d, dir, 2*i+1+!dir, dir? b: (b+e)/2, dir? (b+e)/2: e); return ans; } int leftmost(int l, int r, int d) { return lrmost(l, r, d, 0, 0, 0, sz); } int rightmost(int l, int r, int d) { return lrmost(l, r, d, 1, 0, 0, sz); } } int height[N]; int lsml[N], rsml[N]; int lval[N], rval[N], val[N]; int n; void init_sml() { vector<int> vec; Loop (i,0,n) { while (vec.size() && height[vec.back()] > height[i]) vec.pop_back(); lsml[i] = vec.size()? vec.back(): -1; vec.push_back(i); } vec.clear(); LoopR (i,0,n) { while (vec.size() && height[vec.back()] > height[i]) vec.pop_back(); rsml[i] = vec.size()? vec.back(): n; vec.push_back(i); } } void init_val() { Loop (i,0,n) { lval[i] = lsml[i] == -1? inf: lsml[i] == i-1? 0: rmq_mx.get(lsml[i]+1, i+1).first - height[i]; rval[i] = rsml[i] == n? inf: rsml[i] == i+1? 0: rmq_mx.get(i, rsml[i]).first - height[i]; val[i] = min(lval[i], rval[i]); } seg::init(vector<int>(val, val+n)); } bool darre(int l, int r, int d, int i) { int val = min(lsml[i] < l? inf: lval[i], rsml[i] >= r? inf: rval[i]); return val >= d; } void init(int N, std::vector<int> H) { n = N; Loop (i,0,n) height[i] = H[i]; rmq_mx.init(H); rmq_mn.init(H); init_sml(); init_val(); } int max_towers(int L, int R, int D) { ++R; int ans = seg::get(L, R, D); if (ans == 0) { ans = 1; int p = rmq_mx.get(L, R).second; if (p != L && p != R-1) { int pl = rmq_mn.get(L, p).second; int pr = rmq_mn.get(p+1, R).second; if (darre(L, R, D, pl) && darre(L, R, D, pr)) ans = 2; } return ans; } int pl = seg::leftmost(L, R, D); int pr = seg::rightmost(L, R, D); if (pl != L) { int pll = rmq_mx.get(L, pl).second; if (pll != L) { int plll = rmq_mn.get(L, pll).second; ans += darre(L, R, D, plll); } } if (pr != R-1) { int prr = rmq_mx.get(pr+1, R).second; if (prr != R-1) { int prrr = rmq_mn.get(prr+1, R).second; ans += darre(L, R, D, prrr); } } return ans; }
#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...