Submission #1180587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180587		ByeWorld	Triple Jump (JOI19_jumps)	C++20	0 / 100	4093 ms	52880 KiB

jumps

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 5e5+10;
const int MAXA = 1e9;
const int INF = 2e9+100;
const int SQRT = 500;
const int LOG = 20;
const int MOD = 998244353;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

struct segtree {
	int st[4*MAXN];
	void bd(int id,int l, int r){
		st[id] = INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return INF;
		return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	int upd(int id,int l, int r,int x,int y){
		if(l==r && l==x) return st[id] = y;
		if(r<x || x<l) return st[id];
		return st[id] = min(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} MN;
struct seg {
	int st[4*MAXN];
	void bd(int id,int l, int r){
		st[id] = -INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	int upd(int id,int l, int r,int x,int y){
		if(l==r && l==x) return st[id] = y;
		if(r<x || x<l) return st[id];
		return st[id] = max(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} MX;

int n, a[MAXN], ans[MAXN], st[MAXN][LOG+5];
vector<pii>que[MAXN];

int QUE(int l, int r){
	if(l>r) return -INF;
	int lg = log2(r-l+1);
	return max(st[l][lg], st[r-(1<<lg)+1][lg]);
}
signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i]; st[i][0] = a[i];
	}
	for(int j=1; j<LOG; j++)
		for(int i=1; i+(1<<j)-1<=n; i++)
			st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);

	int Q; cin>>Q;
	for(int P=1; P<=Q; P++){
		int l,r; cin>>l>>r;
		que[l].pb({r, P});
	}
	for(int l=n; l>=1; l--){
		for(auto [r, id] : que[l]){
			int mx = 0;
			for(int x=l; x<=r; x++){
				for(int y=x+1; y<=r; y++){
					chmx(mx, a[x]+a[y]+QUE(y+y-x, n));
					if(a[x] <= a[y]) break;
				}
			}
			ans[id] = mx;
		}
	}
	for(int i=1; i<=Q; i++) cout << ans[i] << '\n';
} 

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