Submission #1316559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316559		boclobanchat	Triple Jump (JOI19_jumps)	C++20	5 / 100	4094 ms	18940 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int A[MAXN],seg[MAXN*4],sp[MAXN][20],vi[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
int rmq(int l,int r)
{
	if(l>r) return -2e9;
	int lg=getlog(r-l+1);
	return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
void build(int l,int r,int pos)
{
	if(l==r)
	{
		seg[pos]=l;
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
	if(A[seg[pos*2]]<A[seg[pos*2+1]]) seg[pos]=seg[pos*2+1];
	else seg[pos]=seg[pos*2];
}
void update(int l,int r,int i,int val,int pos)
{
	if(i<l||r<i) return ;
	if(l==r)
	{
		seg[pos]=val;
		return ;
	}
	int mid=(l+r)/2;
	update(l,mid,i,val,pos*2);
	update(mid+1,r,i,val,pos*2+1);
	if(A[seg[pos*2]]<A[seg[pos*2+1]]) seg[pos]=seg[pos*2+1];
	else seg[pos]=seg[pos*2];
}
int get(int l,int r,int u,int v,int pos)
{
	if(u<=l&&r<=v) return seg[pos];
	int mid=(l+r)/2;
	if(v<=mid) return get(l,mid,u,v,pos*2);
	if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
	int a=get(l,mid,u,v,pos*2),b=get(mid+1,r,u,v,pos*2+1);
	if(A[a]<A[b]) return b;
	return a;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		sp[i][0]=A[i];
	}
	for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n-(1<<j)+1;i++) sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
	cin>>q;
	build(1,n,1);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		int cnt=min(22,r-l+1);
		for(int j=1;j<=cnt;j++) update(1,n,vi[j]=get(1,n,l,r,1),0,1);
		sort(vi+1,vi+cnt+1);
		long long ans=0;
		for(int j=1;j<=cnt;j++) for(int k=j+1;k<=cnt;k++)
			ans=max(ans,1LL*A[vi[j]]+A[vi[k]]+max(max(rmq(max(l,vi[j]*2-vi[k]),vi[j]-1),rmq(vi[j]+1,(vi[j]+vi[k])/2)),rmq(vi[k]*2-vi[j],r)));
		cout<<ans<<"\n";
		for(int j=1;j<=cnt;j++) update(1,n,vi[j],vi[j],1);
	}
}

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