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 <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);
V = (l->V);
trav(y, r->V){
V.push_back(y);
}
sort(all(V));
reverse(all(V));
}
else{
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 = max(l->get_ab(L, R), r->get_ab(L, R));
int x = l->get_min(L,R);
int y = r->get_max(L,R);
return max(res,y-x);
}
int get_ba(int L, int R){
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return ba;
int res = max(l->get_ba(L, R), r->get_ba(L, R));
int x = r->get_min(L,R);
int y = l->get_max(L,R);
return max(res,y-x);
}
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);
}
int first_ab(int L, int R, int D){
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;
}
}
return hi;
}
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);
return (ST->geq(i,R,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 |
---|
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... |