Submission #593409

#	Time	Username	Problem	Language	Result	Execution time	Memory
593409		haojiandan	Triple Jump (JOI19_jumps)	C++14	100 / 100	877 ms	110348 KiB

jumps

// 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;
      |                                     ^~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54