제출 #1180619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180619		ByeWorld	Triple Jump (JOI19_jumps)	C++20	100 / 100	610 ms	76980 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 = 1e9+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 node {
	int ab=-INF, c=-INF, val=-INF;
} NOL;
int a[MAXN];
struct seg {
	node st[4*MAXN];
	void bd(int id,int l, int r){
		if(l==r){
			st[id].c = a[l]; return;
		}
		bd(lf,l,md); bd(rg,md+1,r);
		st[id] = mrg(st[lf], st[rg]);
	}
	node mrg(node a, node b){
		node ret;
		ret.val = max(max(a.val,b.val), a.ab+b.c);
		ret.ab = max(a.ab, b.ab); ret.c = max(a.c, b.c);
		return ret;
	}
	node 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 NOL;
		return mrg(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	node upd(int id,int l, int r,int x,int y){
		if(l==r && l==x){
			chmx(st[id].ab, y);
			chmx(st[id].val, st[id].ab+st[id].c);
			return st[id];
		}
		if(r<x || x<l) return st[id];
		return st[id] = mrg(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} A;

int n, ans[MAXN];
vector<pii>que[MAXN];
vector<int> add[MAXN];

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]; 
	}

	vector<int> stac;
	for(int i=1; i<=n; i++){
		while(!stac.empty() && a[stac.back()] <= a[i]){
			add[stac.back()].pb(i); //upd: nxt greater
			stac.pop_back();
		}
		// if(!stac.empty())
		// 	add[stac.back()].pb(i);
		stac.pb(i);
	}

	stac.clear();
	for(int i=n; i>=1; i--){
		while(!stac.empty() && a[stac.back()] <= a[i]){
			add[i].pb(stac.back()); //upd: prev greater
			stac.pop_back();
		}
		// if(!stac.empty())
		// 	add[stac.back()].pb(i);
		stac.pb(i);
	}

	A.bd(1,1,n);
	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--){
		// vector<int> less;
		// int nxt = -1;
		// for(int x=l+1; x<=n; x++){
		// 	if(a[l] <= a[x]){
		// 		if(nxt == -1){
		// 			nxt = x;
		// 			add[l].pb(nxt);
		// 		}
		// 	}
		// 	else less.pb(x);
		// }
		// int las = -INF;
		// for(auto in : less){
		// 	if(las >= a[in]) continue; // gk opt
		// 	add[l].pb(in);
		// 	las = a[in];
		// }
		for(auto x : add[l]){ // a[l],a[x], ...
			A.upd(1,1,n, x+x-l, a[l]+a[x]);
		}
		for(auto [r, id] : que[l]){	
			ans[id] = A.que(1,1,n,l,r).val;
		}
	}
	for(int i=1; i<=Q; i++) cout << ans[i] << '\n';
} 

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