#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;
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 max(l->get_max(L, R), r->get_max(L, R));
}
int get_min(int L, int R) {
if (R <= lo || hi <= L) return big;
if (L <= lo && hi <= R) return mi;
return min(l->get_min(L, R), r->get_min(L, R));
}
int get_ab(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ab;
int res = (l->get_ab(L, R));
if(res < r->ab){
res = max(res, r->get_ab(L, R));
}
if(res < (r->ma) - (l->mi)){
int x = l->get_min(L,R);
int y = r->get_max(L,R);
res = max(res, y-x);
}
return res;
}
int get_ba(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ba;
int res = l->get_ba(L, R);
if(res < r->ba){
res = max(res, r->get_ba(L, R));
}
if(res < (l->ma) - (r->mi)){
int x = r->get_min(L, R);
int y = l->get_max(L, R);
res = max(res, y-x);
}
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(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;
rep(c1,0,n){
H2.push_back(H[c1]);
HI[H[c1]] = c1;
ind.push_back(c1);
delta.push_back(0);
}
ST = new Segtree(H2, 0, n);
get_ct(0, n);
sort(all(ind), comp);
ST->setup(delta);
}
unordered_map<ll,int> M;
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(ST->get_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(ST->get_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, 7, 1) << "\n";
cout << max_towers(0, 7, 2) << "\n";
cout << max_towers(0, 7, 3) << "\n";
cout << max_towers(0, 7, 10) << "\n";
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
36136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
157 ms |
56908 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
13804 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
36136 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
