#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int inf=1e9+7;
int n, lt[100001], rt[100001], cut[100001], root[100001];
stack<int> stk;
vector<pair<int, int>> v;
vector<int> del, a;
struct maxseg {
int tree[100001*2], sz;
void init(int n) {sz=n;}
void update(int idx, int v) {
for(tree[idx+=sz]+=v; idx>1; idx>>=1) tree[idx>>1]=max(tree[idx], tree[idx^1]);
}
int query(int l, int r) {
int res=0;
for(l+=sz, r+=sz; l<=r; l>>=1, r>>=1) {
if(l&1) res=max(res, tree[l++]);
if(~r&1) res=max(res, tree[r--]);
}
return res;
}
} tree;
struct minseg {
int tree[100001*2], sz;
void init(int n) {
sz=n;
memset(tree, 0x3f, sizeof(tree));
}
void update(int idx, int v) {
for(tree[idx+=sz]+=v; idx>1; idx>>=1) tree[idx>>1]=min(tree[idx], tree[idx^1]);
}
int query(int l, int r) {
int res=0;
for(l+=sz, r+=sz; l<=r; l>>=1, r>>=1) {
if(l&1) res=min(res, tree[l++]);
if(~r&1) res=min(res, tree[r--]);
}
return res;
}
} mtree;
struct PST {
struct Node {
int v, l, r;
};
vector<Node> tree;
void mak() {tree.push_back({0, -1, -1});}
void init(int node, int s, int e) {
if(s==e) return;
tree[node].l=(int)tree.size();
mak();
tree[node].r=(int)tree.size();
mak();
int m=s+e>>1;
init(tree[node].l, s, m);
init(tree[node].r, m+1, e);
}
void update(int node, int s, int e, int idx, int v, int prv) {
if(s>idx || e<idx) return;
tree[node]=tree[prv];
tree[node].v+=v;
if(s==e) return;
int m=s+e>>1;
if(idx<=m) {
tree[node].l=(int)tree.size();
mak();
update(tree[node].l, s, m, idx, v, tree[prv].l);
}
else {
tree[node].r=(int)tree.size();
mak();
update(tree[node].r, m+1, e, idx, v, tree[prv].r);
}
}
int query(int node, int s, int e, int l, int r) {
if(s>r || e<l) return 0;
if(s>=l && e<=r) return tree[node].v;
int m=s+e>>1;
return query(tree[node].l, s, m, l, r)+query(tree[node].r, m+1, e, l, r);
}
} pst;
void init(int N, vector<int> A) {
n=N;
for(auto i: A) a.push_back(i);
tree.init(n);
mtree.init(n);
for(int i=0; i<n; i++) tree.update(i, a[i]);
for(int i=0; i<n; i++) mtree.update(i, a[i]);
for(int i=0; i<n; i++) {
while(!stk.empty() && a[stk.top()]>a[i]) stk.pop();
lt[i]=(stk.empty() ? -1 : stk.top());
stk.push(i);
}
while(!stk.empty()) stk.pop();
for(int i=n-1; i>=0; i--) {
while(!stk.empty() && a[stk.top()]>a[i]) stk.pop();
rt[i]=(stk.empty() ? n : stk.top());
stk.push(i);
}
for(int i=0; i<n; i++) {
int curr=inf;
if(lt[i]>=0) curr=min(curr, tree.query(lt[i]+1, i));
if(rt[i]<n) curr=min(curr, tree.query(i, rt[i]-1));
if(curr==inf) cut[i]=inf;
else if(curr>a[i]) cut[i]=curr-a[i];
else cut[i]=0;
v.push_back({cut[i], i});
del.push_back(cut[i]);
}
del.push_back(inf);
sort(del.begin(), del.end());
sort(v.begin(), v.end());
root[n]=0;
pst.mak();
pst.init(0, 0, n-1);
for(int i=n-1; i>=0; i--) {
root[i]=(int)pst.tree.size();
pst.mak();
pst.update(root[i], 0, n-1, v[i].second, 1, root[i+1]);
}
}
int max_towers(int l, int r, int d) {
if(l==r || r==l+1) return 1;
if(tree.query(l, r)-mtree.query(l, r)<d) return 1;
int cnt=0;
if(rt[l]==n || tree.query(l, rt[l]-1)>=d+a[l]) cnt++;
if(lt[r]==-1 || tree.query(lt[r]+1, r)>=d+a[r]) cnt++;
int idx=lower_bound(del.begin(), del.end(), d)-del.begin();
return cnt+pst.query(root[idx], 0, n-1, l+1, r-1);
}
Compilation message
towers.cpp:28:2: error: extended character is not valid in an identifier
28 | sz=n;
| ^
towers.cpp:28:5: error: extended character is not valid in an identifier
28 | sz=n;
| ^
towers.cpp:28:8: error: extended character is not valid in an identifier
28 | sz=n;
| ^
towers.cpp:29:2: error: extended character is not valid in an identifier
29 | memset(tree, 0x3f, sizeof(tree));
| ^
towers.cpp:29:5: error: extended character is not valid in an identifier
29 | memset(tree, 0x3f, sizeof(tree));
| ^
towers.cpp:29:8: error: extended character is not valid in an identifier
29 | memset(tree, 0x3f, sizeof(tree));
| ^
towers.cpp:29:11: error: extended character is not valid in an identifier
29 | memset(tree, 0x3f, sizeof(tree));
| ^
towers.cpp:30:3: error: extended character is not valid in an identifier
30 | }
| ^
towers.cpp: In member function 'void minseg::init(int)':
towers.cpp:28:2: error: '\U000000a0' was not declared in this scope
28 | sz=n;
| ^
towers.cpp:29:4: error: expected ';' before '\U000000a0'
29 | memset(tree, 0x3f, sizeof(tree));
| ^~
| ;
towers.cpp:30:5: error: expected ';' before '}' token
30 | }
| ^~
| ;
towers.cpp: In member function 'void PST::init(int, int, int)':
towers.cpp:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int m=s+e>>1;
| ~^~
towers.cpp: In member function 'void PST::update(int, int, int, int, int, int)':
towers.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int m=s+e>>1;
| ~^~
towers.cpp: In member function 'int PST::query(int, int, int, int, int)':
towers.cpp:79:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int m=s+e>>1;
| ~^~
