제출 #208619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208619		super_j6	3단 점프 (JOI19_jumps)	C++14	100 / 100	1552 ms	111608 KiB

jumps

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define pii pair<int, pi>
#define f first
#define s second

struct segTree{
	int l, r;
	segTree *left, *right;
	pii val = {0, {0, 0}};
	
	segTree(int a, int b){
		l = a;
		r = b;
		
		if(l != r){
			int mid = (l + r) / 2;
			left = new segTree(l, mid);
			right = new segTree(mid + 1, r);
		}
	}
	
	pii pull(pii lq, pii rq){
		return {max(lq.s.f + rq.s.s, max(lq.f, rq.f)), {max(lq.s.f, rq.s.f), max(lq.s.s, rq.s.s)}};
	}
	
	void add(int x, pi v){
		if(x < l || r < x) return;
		if(l == r){
			val.s.f = max(val.s.f, v.f);
			val.s.s = max(val.s.s, v.s);
			val.f = val.s.f + val.s.s;
			return;
		}
		
		left->add(x, v);
		right->add(x, v);
		val = pull(left->val, right->val);
	}
	
	pii qry(int a, int b){
		if(r < a || b < l) return {0, {0, 0}};
		if(a <= l && r <= b) return val;
		
		return pull(left->qry(a, b), right->qry(a, b));
	}
};

const int maxn = 500000;
int n, q;
int a[maxn];
vector<int> p[maxn];
vector<pi> qry[maxn];
int ans[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	stack<int> stk;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		while(!stk.empty()){
			int j = stk.top(), k = 2 * i - j;
			if(k < n) p[j].push_back(k);
			if(a[j] <= a[i]) stk.pop();
			else break;
		}
		stk.push(i);
	}
	
	cin >> q;
	
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--, r--;
		qry[l].push_back({r, i});
	}
	
	segTree tre(0, n);
	for(int i = n - 1; i >= 0; i--){
		tre.add(i, {0, a[i]});
		for(int j : p[i]) tre.add(j, {a[i] + a[(i + j) / 2], 0});
		for(pi j : qry[i]) ans[j.s] = tre.qry(i, j.f).f;
	}
	
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

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