#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using indexed_set = tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;
const int MAXN = 1e5, half = 1e5+1;
int n,a[MAXN],maxi[200003],mini[200003];
vector<int> possibleDeltas;
vector<pair<int,int>> answers;
indexed_set segt[200003];
struct item{
int l,r,nb;
};
struct comp{
int min,max,diff;
};
comp diffl[400010], diffr[400010];
item query(int l, int r, int L, int R){
l += half;
r += half;
item ans = item{INT_MAX,0,0};
while (l <= r){
if (l&1){
int idx1 = segt[l].order_of_key(L);
int idx2 = segt[l].order_of_key(R+1)-1;
ans.nb += max(0,idx2-idx1);
ans.r = max(ans.r,*segt[l].find_by_order(idx2));
ans.l = min(ans.l,*segt[l].find_by_order(idx1));
l++;
}
if (r%2 == 0){
int idx1 = segt[r].order_of_key(L);
int idx2 = segt[r].order_of_key(R+1)-1;
ans.nb += max(0,idx2-idx1);
ans.r = max(ans.r,*segt[r].find_by_order(idx2));
ans.l = min(ans.l,*segt[r].find_by_order(idx1));
r--;
}
l >>= 1;
r >>= 1;
}
return ans;
}
void add(int node, int val){
node += half;
segt[node].insert(val);
node >>= 1;
while (node){
segt[node].insert(val);
node >>= 1;
}
}
void modify(int idx, int val){
idx += n;
idx >>= 1;
maxi[idx] = val;
while (idx){
maxi[idx] = max(maxi[2*idx],maxi[2*idx+1]);
idx >>= 1;
}
}
int max_query(int l, int r){
l += n;
r += n;
int ans = 0;
while (l <= r){
if (l&1){
ans = max(ans,maxi[l]);
l++;
}
if (r%2 == 0){
ans = max(ans,maxi[r]);
r--;
}
}
return ans;
}
void build_left(int idx, int l, int r){
if (l == r){
diffl[idx] = comp{a[l],a[l],0};
return;
}
int mid = (l+r)/2;
build_left(2*idx,l,mid);
build_left(2*idx+1,mid+1,r);
diffl[idx].max = max(diffl[2*idx].max,diffl[2*idx+1].max);
diffl[idx].min = min(diffl[2*idx].min,diffl[2*idx+1].min);
diffl[idx].diff = max({diffl[2*idx].diff,diffl[2*idx+1].diff,diffl[2*idx+1].max-diffl[2*idx].min});
}
void build_right(int idx, int l, int r){
if (l == r){
diffr[idx] = comp{a[l],a[l],0};
return;
}
int mid = (l+r)/2;
build_right(2*idx,l,mid);
build_right(2*idx+1,mid+1,r);
diffr[idx].max = max(diffr[2*idx].max,diffr[2*idx+1].max);
diffr[idx].min = min(diffr[2*idx].min,diffr[2*idx+1].min);
diffr[idx].diff = max({diffr[2*idx].diff,diffr[2*idx+1].diff,diffr[2*idx].max-diffr[2*idx+1].min});
}
int query_left(int idx, int l, int r, int L, int R){
if (r < L or l > R) return -1;
if (l >= L and r <= R) return diffl[idx].diff;
int mid = (l+r)/2;
return max(query_left(2*idx,l,mid,L,R),query_left(2*idx+1,mid+1,r,L,R));
}
int query_right(int idx, int l, int r, int L, int R){
if (r < L or l > R) return -1;
if (l >= L and r <= R) return diffr[idx].diff;
int mid = (l+r)/2;
return max(query_right(2*idx,l,mid,L,R),query_right(2*idx+1,mid+1,r,L,R));
}
void init(int N, vector<int> H){
n = N;
vector<pair<int,int>> v,deltas;
for (int i=0; i<n; ++i){
v.emplace_back(H[i],i);
a[i] = H[i];
modify(i,a[i]);
}
sort(v.begin(),v.end());
set<int> pos = {INT_MIN,INT_MAX};
for (auto i:v){
auto it = pos.upper_bound(i.second);
int A = *it,maxi=INT_MAX;
it--;
int B = *it;
bool ok = false;
if (A != INT_MAX){
if (i.second == A-1) ok = true;
maxi = min(maxi,max_query(i.second,A));
}
if (B != INT_MIN){
if (B == i.second-1) ok = true;
maxi = min(maxi,max_query(B,i.second));
}
if (maxi != i.first and !ok){
if (maxi == INT_MAX){
possibleDeltas.emplace_back(maxi);
deltas.emplace_back(maxi,i.second);
}
else{
possibleDeltas.emplace_back(maxi-i.first);
deltas.emplace_back(maxi-i.first,i.second);
}
possibleDeltas.emplace_back(maxi);
}
pos.emplace(i.second);
}
possibleDeltas.emplace_back(INT_MAX);
sort(possibleDeltas.begin(),possibleDeltas.end());
possibleDeltas.erase(unique(possibleDeltas.begin(),possibleDeltas.end()),possibleDeltas.end());
for (auto i:deltas){
int idx = lower_bound(possibleDeltas.begin(),possibleDeltas.end(),i.first)-possibleDeltas.begin();
add(idx,i.second);
}
for (int i=0; i<possibleDeltas.size(); ++i){
add(i,INT_MAX);
add(i,INT_MIN);
}
build_left(1,0,n-1);
build_right(1,0,n-1);
}
int max_towers(int L, int R, int D){
int from = lower_bound(possibleDeltas.begin(),possibleDeltas.end(),D)-possibleDeltas.begin();
item res = query(from,possibleDeltas.size()-1,L,R);
int deb = L, fin = res.l-1, ansL = -1;
while (deb <= fin){
int mid = (deb+fin)/2;
if (max_query(mid,res.l)-a[res.l] >= D){
deb = mid+1;
ansL = mid;
}
else fin = mid-1;
}
bool has1 = 0, has2 = 0;
if (query_left(1,0,n-1,L,ansL) >= D) has1 = true;
deb = res.r+1, fin = R;
int ansR = -1;
while (deb <= fin){
int mid = (deb+fin)/2;
if (max_query(res.r,mid)-a[res.r] >= D){
fin = mid-1;
ansR = mid;
}
else deb = mid+1;
}
if (query_right(1,0,n-1,res.r,R) >= D) has2 = true;
return res.nb+has1+has2;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:173:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for (int i=0; i<possibleDeltas.size(); ++i){
| ~^~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:196:6: warning: variable 'ansR' set but not used [-Wunused-but-set-variable]
196 | int ansR = -1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4064 ms |
17488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4099 ms |
15952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4099 ms |
15952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4046 ms |
18400 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4093 ms |
16700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4099 ms |
15952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4064 ms |
17488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
