#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll big = 1000000007;
const int MAXN = 100001;
int n;
vi H2;
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ() {}
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
RMQ<int> min_rmq, max_rmq;
int get_min2(int L, int R){
return min_rmq.query(L, R);
}
int get_max2(int L, int R){
return -max_rmq.query(L, R);
}
struct Segtree {
Segtree *l = 0, *r = 0;
int lo, hi, ma = -big, mi = big, ab = 0, ba = 0;
vi V = {};
Segtree(vi& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo)/2;
l = new Segtree(v, lo, mid); r = new Segtree(v, mid, hi);
ma = max(l->ma, r->ma);
mi = min(l->mi, r->mi);
ab = max(l->ab, r->ab);
ab = max(ab, (r->ma) - (l->mi));
ba = max(l->ba, r->ba);
ba = max(ba, (l->ma) - (r->mi));
}
else{
ma = v[lo];
mi = v[lo];
}
}
void setup(vi &v){
if(lo + 1 < hi){
l->setup(v);
r->setup(v);
int x = 0;
int y = 0;
while(x < sz(l->V) || y < sz(r->V)){
if(y == sz(r->V) || (x < sz(l->V) && l->V[x] >= r->V[y])){
V.push_back(l->V[x]);
x++;
}
else{
V.push_back(r->V[y]);
y++;
}
}
}
else{
if(v[lo] > 0){V = {v[lo]};}
}
}
int get_max(int L, int R) {
if (R <= lo || hi <= L) return -big;
if (L <= lo && hi <= R) return ma;
return get_max2(L, R);
}
int get_min(int L, int R) {
if (R <= lo || hi <= L) return big;
if (L <= lo && hi <= R) return mi;
return get_min2(L, R);
}
int get_ab(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ab;
int x = l->get_min(L,R);
int y = r->get_max(L,R);
int res = y-x;
if(res < r->ab){
res = max(res, r->get_ab(L, R));
}
if(res < l->ab){
res = max(res, l->get_ab(L, R));
}
return res;
}
int get_ba(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ba;
int x = r->get_min(L,R);
int y = l->get_max(L,R);
int res = y-x;
if(res < r->ba){
res = max(res, r->get_ba(L, R));
}
if(res < l->ba){
res = max(res, l->get_ba(L, R));
}
return res;
}
int geq(int L, int R, int D){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R){
int lo = 0;
int hi = sz(V);
if(sz(V) == 0)return 0;
if(V[0] < D)return 0;
while(lo < hi-1){
int mid = (lo + hi) / 2;
if(V[mid] < D){
hi = mid;
}
else{
lo = mid;
}
}
return hi;
}
return (l->geq(L, R, D)) + (r->geq(L, R, D));
}
};
Segtree *ST;
map<int,int> HI;
vi delta;
vi ind;
void get_ct(int L, int R){
if(L >= R)return;
if(L == R-1){
delta[L] = 0;
return;
}
int i = HI[ST->get_max(L, R)];
int x = ST->get_min(L,i);
int y = ST->get_min(i+1,R);
delta[i] = H2[i]-max(x, y);
delta[i] = max(delta[i], 0);
get_ct(L, i);
get_ct(i+1,R);
}
bool comp(int i, int j){
return delta[i] > delta[j];
}
void init(int N, vi H){
n = N;
vi H3;
rep(c1,0,n){
H2.push_back(H[c1]);
HI[H[c1]] = c1;
H3.push_back(-H[c1]);
ind.push_back(c1);
delta.push_back(0);
}
ST = new Segtree(H2, 0, n);
min_rmq = RMQ<int>(H2);
max_rmq = RMQ<int>(H3);
get_ct(0, n);
sort(all(ind), comp);
ST->setup(delta);
}
//unordered_map<ll,int> M;
const int lim = 10;
int AB(int L, int R){
if(R-L > lim)return ST->get_ab(L,R);
int mi = big;
int res = 0;
rep(c1,L,R){
mi = min(mi, H2[c1]);
res = max(H2[c1]-mi, res);
}
return res;
}
int BA(int L, int R){
if(R-L > lim)return ST->get_ba(L, R);
int ma = -big;
int res = 0;
rep(c1,L,R){
ma = max(ma, H2[c1]);
res = max(ma-H2[c1], res);
}
return res;
}
int first_ab(ll L, ll R, ll D){
// ll h = 2*(L*big + D);
// if(M.find(h) != M.end())return M[h];
int lo = L;
int hi = R;
while(lo < hi-1){
int mid = (lo+hi)/2;
if(AB(L, mid+1) < D){
lo = mid;
}
else{
hi = mid;
}
}
// M[h] = hi;
return hi;
}
int last_ba(ll L, ll R, ll D){
// ll h = 2*(R*big + D) + 1;
// if(M.find(h) != M.end())return M[h];
int lo = L;
int hi = R;
while(lo < hi-1){
int mid = (lo+hi)/2;
if(BA(mid, R) >= D){
lo = mid;
}
else{
hi = mid;
}
}
// M[h] = lo;
return lo;
}
int max_towers(int L, int R, int D){
R++;
if(ST->get_ab(L, R) < D || ST->get_ba(L, R) < D)return 1;
int i = first_ab(L, R, D);
int j = last_ba(L, R, D)+1;
return (ST->geq(i,j,D))+1;
}
/*
int main() {
int N;
N = 7;
vi H = {1,4,2,9,3,6,5};
init(N,H);
cout << max_towers(0, 6, 1) << "\n";
cout << max_towers(0, 6, 2) << "\n";
cout << max_towers(0, 6, 3) << "\n";
cout << max_towers(0, 6, 10) << "\n";
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42140 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
720 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
720 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
70792 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
16672 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
720 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42140 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
