Submission #256168

#	Time	Username	Problem	Language	Result	Execution time	Memory
256168		Atalasion	Triple Jump (JOI19_jumps)	C++14	100 / 100	1202 ms	86184 KiB

jumps

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

struct node{
	int mx, num, ans;
};

struct query{
	int id, R;
};

int n, m, a[N], lazy[N << 2], ans[N];
node seg[N << 2];
vector<query> L[N];

node merge(node x, node y){
	node res = x;
	res.mx = max(res.mx, y.mx);
	res.num = max(res.num, y.num);
	res.ans = max(res.ans, y.ans);
	return res;
}

void modify(int id, int x){
	seg[id].mx = x;
	seg[id].ans = seg[id].mx + seg[id].num;
	lazy[id] = x;
}

void shift(int id){
	if (lazy[id] == -1) return;
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = -1;
}

void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].mx = seg[id].ans = 0;
		seg[id].num = a[l];
		return;
	}
	int md = (l + r) >> 1;
	build(id << 1, l, md);
	build(id << 1 | 1, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

int BS(int id, int x, int l, int r){
	if (r - l == 1){
//		cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
		if (seg[id].mx < x) return n + 1;
		return l;
	}
	shift(id);
	int md = (l + r) >> 1;
	if (seg[id << 1].mx >= x) return BS(id << 1, x, l, md);
	return BS(id << 1 | 1, x, md, r);
}

void Set(int id, int lq, int rq, int x, int l, int r){
	if (rq <= lq) return;
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		modify(id, x);
//		cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
		return;
	}
	int md = (l + r) >> 1;
	shift(id);
	Set(id << 1, lq, rq, x, l, md);
	Set(id << 1 | 1, lq, rq, x, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

int get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		return seg[id].ans;
	}
	shift(id);
	int md = (l + r) >> 1;
	return max(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++){
		int l, r;
		cin >> l >> r;
		query res;
		res.id = i, res.R = r;
		L[l].pb(res);
	}
	build(1, 1, n + 1);
//	cout << "YES" << endl;
	stack<int> st;
	st.push(n);
	for (int i = n - 1; i >= 1; i--){
//		cout << i << endl;
		while (st.size() && a[st.top()] <= a[i]){
			int sm = a[i] + a[st.top()];
			int l = i, r = st.top();
			int R = 2 * r - l;
			if (R <= n){
//				cout << "YES" << endl;
				int koj = BS(1, sm, 1, n + 1);
//				cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
				Set(1, R, koj, sm, 1, n + 1);
//				cout << "YES2" << endl;
			}
			st.pop();
			
		}
//		cout << "YES2" << endl;
		if (st.size()){
			int sm = a[i] + a[st.top()];
			int l = i, r = st.top();
			int R = 2 * r - l;
			if (R <= n){
				int koj = BS(1, sm, 1, n + 1);
//				cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
				Set(1, R, koj, sm, 1, n + 1);
			}
		}
		st.push(i);
		for (auto u:L[i]) ans[u.id] = get(1, i, u.R + 1, 1, n + 1);
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';








	return 0;
}

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