This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const ll INF=1e10;
const int maxn=(5e5)+10;
int n,a[maxn];
int q,st[maxn],tot;
struct node {
int r,id;
};
vector<int> A[maxn];
vector<node> g[maxn];
ll ans[maxn];
namespace Seg {
ll mx[maxn*4],tr[maxn*4],MX[maxn*4];
ll lazy[maxn*4];
void pushup(int root) {
tr[root]=max(tr[root<<1],tr[root<<1|1]);
mx[root]=max(mx[root<<1],mx[root<<1|1]);
MX[root]=max(MX[root<<1],MX[root<<1|1]);
}
void build(int l,int r,int root) {
tr[root]=mx[root]=lazy[root]=-INF;
if (l==r) { MX[root]=a[l]; return; }
int mid=(l+r)>>1;
build(l,mid,root<<1),build(mid+1,r,root<<1|1);
pushup(root);
}
void puttag(int root,ll delta) {
tr[root]=delta+MX[root],mx[root]=lazy[root]=delta;
}
void pushdown(int root) {
if (lazy[root]!=-INF) puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]),lazy[root]=-INF;
}
void update(int L,int R,int l,int r,int root,ll delta) {
if (L>R) return;
if (L<=l&&r<=R) { puttag(root,delta); return; }
int mid=(l+r)>>1; pushdown(root);
if (L<=mid) update(L,R,l,mid,root<<1,delta);
if (mid<R) update(L,R,mid+1,r,root<<1|1,delta);
pushup(root);
}
int query(int L,int R,int l,int r,int root,ll delta) {
if (mx[root]<=delta) return n+1;
if (L<=l&&r<=R) {
if (l==r) return l;
int mid=(l+r)>>1; pushdown(root);
if (mx[root<<1]>delta) return query(L,R,l,mid,root<<1,delta);
return query(L,R,mid+1,r,root<<1|1,delta);
}
int mid=(l+r)>>1;
pushdown(root);
int res=n+1;
if (L<=mid) {
res=query(L,R,l,mid,root<<1,delta);
if (res!=n+1) return res;
}
if (mid<R) res=query(L,R,mid+1,r,root<<1|1,delta);
return res;
}
ll query(int L,int R,int l,int r,int root) {
if (L<=l&&r<=R) return tr[root];
int mid=(l+r)>>1; pushdown(root);
ll res=-INF;
if (L<=mid) res=max(res,query(L,R,l,mid,root<<1));
if (mid<R) res=max(res,query(L,R,mid+1,r,root<<1|1));
return res;
}
};
int main() {
//freopen("1.txt","r",stdin);
read(n);
for (int i=1;i<=n;i++) read(a[i]);
for (int i=1;i<=n;i++) {
while (tot&&a[st[tot]]<a[i]) tot--;
if (tot) A[st[tot]].push_back(i); st[++tot]=i;
}
tot=0;
for (int i=n;i>=1;i--) {
while (tot&&a[st[tot]]<a[i]) tot--;
if (tot) A[i].push_back(st[tot]); st[++tot]=i;
}
read(q);
for (int i=1;i<=q;i++) {
int x,y; read(x),read(y);
g[x].push_back((node){y,i});
}
Seg::build(1,n,1);
for (int i=n;i>=1;i--) {
for (int &j : A[i]) if (j*2-i<=n) {
// printf("i=%d,j=%d\n",i,j);
int R=Seg::query(j*2-i,n,1,n,1,a[i]+a[j])-1;
Seg::update(j*2-i,R,1,n,1,a[i]+a[j]);
}
for (node &A : g[i]) {
ans[A.id]=Seg::query(1,A.r,1,n,1);
}
}
for (int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
Compilation message (stderr)
jumps.cpp: In function 'int main()':
jumps.cpp:89:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
89 | if (tot) A[st[tot]].push_back(i); st[++tot]=i;
| ^~
jumps.cpp:89:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
89 | if (tot) A[st[tot]].push_back(i); st[++tot]=i;
| ^~
jumps.cpp:94:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
94 | if (tot) A[i].push_back(st[tot]); st[++tot]=i;
| ^~
jumps.cpp:94:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
94 | if (tot) A[i].push_back(st[tot]); st[++tot]=i;
| ^~
# | 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... |