#include "towers.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "stub.cpp"
#endif
#define ar array
typedef int64_t ll;
//~ #define int ll
const int inf = 1e9 + 7;
const int N = 1e5 + 5;
const int B = 320;
//~ int first, mount;
//~ vector<int> a, l, r, res;
vector<ar<int, 2>> res;
vector<int> a, tot;
struct STMx{
vector<int> tree;
int N;
STMx(int N): N(N){
tree.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx){
tree[x] = v;
return;
}
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int get(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l){
return -(N << 2);
}
if(lx >= l && rx <= r){
return tree[x];
}
int m = (lx + rx) >> 1;
return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
}
int get(int l, int r){
return get(l, r, 0, N, 1);
}
int first(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(tree[x] < v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(tree[x << 1] >= v) return first(l, r, v, lx, m, x << 1);
else return first(l, r, v, m + 1, rx, x << 1 | 1);
}
int m = (lx + rx) >> 1;
int res = first(l, r, v, lx, m, x << 1);
if(res == -1) res = first(l, r, v, m + 1, rx, x << 1 | 1);
return res;
}
int first(int l, int r, int v){
return first(l, r, v, 0, N, 1);
}
int last(int l, int r, int v, int lx, int rx, int x){
if(lx > r || rx < l) return -1;
if(lx >= l && rx <= r){
if(tree[x] < v) return -1;
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(tree[x << 1 | 1] >= v) return last(l, r, v, m + 1, rx, x << 1 | 1);
else return last(l, r, v, lx, m, x << 1);
}
int m = (lx + rx) >> 1;
int res = last(l, r, v, m + 1, rx, x << 1 | 1);
if(res == -1) res = last(l, r, v, lx, m, x << 1);
return res;
}
int last(int l, int r, int v){
return last(l, r, v, 0, N, 1);
}
}Max(N);
struct ST{
vector<int> Max, Min, t01, t10;
int N;
ST(int N): N(N){
Max.resize(N << 2);
Min.resize(N << 2);
t01.resize(N << 2);
t10.resize(N << 2);
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx){
t01[x] = t10[x] = 0;
Max[x] = Min[x] = v;
return;
}
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
t01[x] = max({t01[x << 1], t01[x << 1 | 1], Max[x << 1 | 1] - Min[x << 1]});
t10[x] = max({t10[x << 1], t10[x << 1 | 1], Max[x << 1] - Min[x << 1 | 1]});
Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
int mn, mx;
int get01(int l, int r, int d, int lx, int rx, int x){
if(lx > r || rx < l){
return -1;
}
if(lx >= l && rx <= r){
if(t01[x] < d && Max[x] - mn < d){
mn = min(mn, Min[x]);
return -1;
}
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Max[x << 1] - mn >= d || t01[x << 1] >= d){
return get01(l, r, d, lx, m, x << 1);
} else {
mn = min(mn, Min[x << 1]);
return get01(l, r, d, m + 1, rx, x << 1 | 1);
}
}
int m = (lx + rx) >> 1;
int res = get01(l, r, d, lx, m, x << 1);
if(res == -1) res = get01(l, r, d, m + 1, rx, x << 1 | 1);
return res;
}
int get01(int l, int r, int d){
mn = inf;
return get01(l, r, d, 0, N, 1);
}
int get10(int l, int r, int d, int lx, int rx, int x){
if(lx > r || rx < l){
return -1;
}
if(lx >= l && rx <= r){
if(t10[x] < d && Max[x] - mn < d){
mn = min(mn, Min[x]);
return -1;
}
if(lx == rx) return lx;
int m = (lx + rx) >> 1;
if(Max[x << 1 | 1] - mn >= d || t10[x << 1 | 1] >= d){
return get10(l, r, d, m + 1, rx, x << 1 | 1);
} else {
mn = min(mn, Min[x << 1 | 1]);
return get10(l, r, d, lx, m, x << 1);
}
}
int m = (lx + rx) >> 1;
int res = get10(l, r, d, m + 1, rx, x << 1 | 1);
if(res == -1) res = get10(l, r, d, lx, m, x << 1);
return res;
}
int get10(int l, int r, int d){
mn = inf;
return get10(l, r, d, 0, N, 1);
}
}tree(N);
int cnt[B][N];
struct sqrtDec{
int a[N];
sqrtDec(){
memset(a, 0, sizeof a);
memset(cnt, 0, sizeof cnt);
}
//~ sqrtDec(int N, int B): N(N), B(B){
//~ a.resize(N);
//~ cnt.resize(B, vector<int>(N + 1));
//~ }
void set(int i, int v){
a[i] = v;
cnt[i / B][v]++;
}
void build(){
for(int i=0;i<B;i++){
for(int j=N-1;j>=0;j--){
cnt[i][j] += cnt[i][j + 1];
}
}
}
int get(int l, int r, int v){
int l_ = l / B, r_ = r / B;
int res = 0;
for(int j=l_+1;j<r_;j++){
res += cnt[j][v];
}
if(l_ == r_){
for(int i=l;i<=r;i++){
res += (a[i] >= v);
}
} else {
for(int i=l;i<(l_+1)*B;i++){
res += (a[i] >= v);
}
for(int i=r_*N;i<=r;i++){
res += (a[i] >= v);
}
}
return res;
}
int first(int l, int r, int v){
int l_ = l / B, r_ = r / B;
for(int i=l;i<min(r + 1, (l_ + 1) * B);i++){
if(a[i] >= v) return i;
}
for(int j=l_ + 1;j<r_;j++){
if(cnt[j][v]){
for(int k=j*B;k<(j+1)*B;k++){
if(a[k] >= v) return k;
}
}
}
for(int i=r_*B;i<=r;i++){
if(a[i] >= v) return i;
}
assert(false);
}
int last(int l, int r, int v){
int l_ = l / B, r_ = r / B;
for(int i=r;i>=max(l, r_*B);i--){
if(a[i] >= v) return i;
}
for(int j=r_-1;j>l_;j--){
if(cnt[j][v]){
for(int k=(j+1)*B-1;k>=j*B;k--){
if(a[k] >= v) return k;
}
}
}
for(int i=(l_ + 1) * B - 1;i>=l;i--){
if(a[i] >= v) return i;
}
assert(false);
}
}block;
void init(int n, vector<int> h) {
a = h;
vector<int> pos;
for(int i=0;i<n;i++){
Max.set(i, a[i]);
if((!i || a[i] < a[i - 1]) && (i + 1 == n || a[i] < a[i + 1])){
pos.push_back(i);
}
}
set<int> ss;
multiset<ar<int, 2>> dif;
for(int i=0;i<(int)pos.size();i++){
if(i){
int mx = Max.get(pos[i - 1], pos[i]);
dif.insert({mx - a[pos[i - 1]], pos[i - 1]});
dif.insert({mx - a[pos[i]], pos[i]});
}
ss.insert(pos[i]);
}
while(!dif.empty()){
auto [d, i] = *dif.begin();
res.push_back({d, i});
//~ cout<<i<<" "<<d<<"\n";
auto it = ss.lower_bound(i);
auto R = it; R++;
if(it == ss.begin() || R == ss.end()){
if(it == ss.begin()){
int mx = Max.get(*it, *R);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*R], *R}));
} else {
auto L = it; L--;
int mx = Max.get(*L, *it);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*L], *L}));
}
ss.erase(it);
continue;
}
auto L = it; --L;
int mx = Max.get(*L, *it);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*L], *L}));
mx = Max.get(*it, *R);
dif.erase(dif.find({mx - a[*it], *it}));
dif.erase(dif.find({mx - a[*R], *R}));
mx = Max.get(*L, *R);
dif.insert({mx - a[*L], *L});
dif.insert({mx - a[*R], *R});
ss.erase(it);
}
res.push_back({inf, *ss.begin()});
for(auto x : res) tot.push_back(x[0]);
tot.erase(unique(tot.begin(), tot.end()), tot.end());
vector<int> v(n);
for(auto [d, i] : res){
v[i] = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1;
}
for(int i=0;i<n;i++){
tree.set(i, a[i]);
assert(v[i] <= N);
block.set(i, v[i]);
}
block.build();
}
int max_towers(int l, int r, int d) {
int D = lower_bound(tot.begin(), tot.end(), d) - tot.begin() + 1;
int n = a.size();
//~ assert(l_ == 0 && r_ == n - 1);
//~ int j = lower_bound(res.begin(), res.end(), (ar<int, 2>){d, 0}) - res.begin();
//~ return (int)res.size() - j;
int res = block.get(l, r, D);
if(!res){
int l_ = tree.get01(l, r, d), r_ = tree.get10(l, r, d);
if(~l_ && ~r_ && l_ <= r_){
return 2;
}
return 1;
}
int l_ = block.first(l, r, D), r_ = block.last(l, r, D);
l_ = Max.last(l, l_, a[l_] + d);
r_ = Max.first(r_, r, a[r_] + d);
//~ cout<<l_<<" "<<r_<<"\n";
if(~l_ && ~tree.get01(l, l_, d)){
res++;
}
if(~r_ && ~tree.get10(r_, r, d)){
res++;
}
return res;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:368:10: warning: unused variable 'n' [-Wunused-variable]
368 | int n = a.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
239 ms |
271968 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
133728 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
133832 KB |
1st lines differ - on the 1st token, expected: '292', found: '648' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
133728 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
133832 KB |
1st lines differ - on the 1st token, expected: '292', found: '648' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
868 ms |
140388 KB |
1st lines differ - on the 1st token, expected: '11903', found: '35594' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
135332 KB |
1st lines differ - on the 1st token, expected: '7197', found: '22584' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
133728 KB |
Output is correct |
| 2 |
Incorrect |
113 ms |
133832 KB |
1st lines differ - on the 1st token, expected: '292', found: '648' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
239 ms |
271968 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
