This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |