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 "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+10;
const int maxm=maxn*40;
const int INF=2e9;
int n,h[maxn],tot,st[maxn];
int mx[maxn*4],ls[maxm],rs[maxm],tr[maxm];
void build(int l,int r,int root) {
if (l==r) { mx[root]=h[l]; return; }
int mid=(l+r)>>1;
build(l,mid,root<<1),build(mid+1,r,root<<1|1);
mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
int querymx(int L,int R,int l,int r,int root) {
if (L>R) return -INF;
if (L<=l&&r<=R) return mx[root];
int mid=(l+r)>>1,res=0;
if (L<=mid) res=querymx(L,R,l,mid,root<<1);
if (mid<R) res=max(res,querymx(L,R,mid+1,r,root<<1|1));
return res;
}
int L[maxn],R[maxn],rt[maxn];
namespace Seg {
int mxR[maxn*4],mxL[maxn*4];
void build(int l,int r,int root) {
if (l==r) { mxR[root]=R[l],mxL[root]=L[l]; return; }
int mid=(l+r)>>1;
build(l,mid,root<<1),build(mid+1,r,root<<1|1);
mxR[root]=max(mxR[root<<1],mxR[root<<1|1]);
mxL[root]=max(mxL[root<<1],mxL[root<<1|1]);
}
int query1(int L,int R,int l,int r,int root,int delta) {
if (mxR[root]<delta) return n+1;
if (L<=l&&r<=R) {
if (l==r) return l;
int mid=(l+r)>>1;
if (mxR[root<<1]>=delta) return query1(L,R,l,mid,root<<1,delta);
return query1(L,R,mid+1,r,root<<1|1,delta);
}
int mid=(l+r)>>1,res=n+1;
if (L<=mid) { res=query1(L,R,l,mid,root<<1,delta); if (res<=n) return res; }
if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
}
int query2(int L,int R,int l,int r,int root,int delta) {
if (mxL[root]<delta) return 0;
if (L<=l&&r<=R) {
if (l==r) return l;
int mid=(l+r)>>1;
if (mxL[root<<1|1]>=delta) return query2(L,R,mid+1,r,root<<1|1,delta);
return query2(L,R,l,mid,root<<1,delta);
}
int mid=(l+r)>>1,res=0;
if (mid<R) { res=query2(L,R,mid+1,r,root<<1|1,delta); if (res) return res; }
if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
}
};
void add(int x,int l,int r,int &root) {
tot++; ls[tot]=ls[root],rs[tot]=rs[root],tr[tot]=tr[root]+1; root=tot;
if (l==r) return;
int mid=((ll)l+r)>>1;
if (x<=mid) add(x,l,mid,ls[root]); else add(x,mid+1,r,rs[root]);
}
int query(int L,int R,int l,int r,int x,int y) {
if (L<=l&&r<=R) return tr[y]-tr[x];
int res=0,mid=((ll)l+r)>>1;
if (L<=mid) res+=query(L,R,l,mid,ls[x],ls[y]);
if (mid<R) res+=query(L,R,mid+1,r,rs[x],rs[y]);
return res;
}
void init(int _n, vector<int> H) {
n=_n;
for (int i=1;i<=n;i++) h[i]=H[i-1];
build(1,n,1);
for (int i=1;i<=n;i++) {
while (tot&&h[st[tot]]>h[i]) tot--;
if (!tot) L[i]=INF; else {
L[i]=querymx(st[tot]+1,i-1,1,n,1);
if (L[i]>=0) L[i]-=h[i];
}
st[++tot]=i;
}
tot=0;
for (int i=n;i>=1;i--) {
while (tot&&h[st[tot]]>h[i]) tot--;
if (!tot) R[i]=INF; else {
R[i]=querymx(i+1,st[tot]-1,1,n,1);
if (R[i]>=0) R[i]-=h[i];
}
st[++tot]=i;
}
Seg::build(1,n,1);
for (int i=1;i<=n;i++) rt[i]=rt[i-1],add(min(L[i],R[i]),-INF,INF,rt[i]);
}
int max_towers(int l, int r, int D) {
l++,r++;
l=Seg::query1(l,n,1,n,1,D);
r=Seg::query2(1,r,1,n,1,D);
if (l>r) return 1;
return 2+(l+1<=r-1?query(D,INF,-INF,INF,rt[l],rt[r-1]):0);
}
Compilation message (stderr)
towers.cpp: In function 'int Seg::query1(int, int, int, int, int, int)':
towers.cpp:44:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
44 | if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
| ^~
towers.cpp:44:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
44 | if (mid<R) res=query1(L,R,mid+1,r,root<<1|1,delta); return res;
| ^~~~~~
towers.cpp: In function 'int Seg::query2(int, int, int, int, int, int)':
towers.cpp:56:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
56 | if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
| ^~
towers.cpp:56:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
56 | if (L<=mid) res=query2(L,R,l,mid,root<<1,delta); return res;
| ^~~~~~
# | 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... |