Submission #950601

#	Time	Username	Problem	Language	Result	Execution time	Memory
950601		pragmatist	Triple Jump (JOI19_jumps)	C++17	19 / 100	4035 ms	43564 KiB

jumps

#include<bits/stdc++.h>

using namespace std;

const int N = (int)5e5+7;
const int M = (int)2e5+7;
const int inf = (int)1e9+7;

int n, q, a[N], b[N], ans[N];
pair<int, int> suf[N];
int L[N], R[N];
vector<pair<int, int> > Q[N];
vector<int> adj[N];

void upd(int l, int r, int x) {
	for(int i = l; i <= r; ++i) {
		b[i] = max(b[i], x);
	}	
}

int get(int l, int r) {
	int res=0;
	for(int i = l; i <= r; ++i) {
		res = max(res, a[i]+b[i]);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	} 
	cin >> q;
    stack<int> st;
	for(int i = 1; i <= n; ++i) {
		L[i] = i;
		while(!st.empty() && a[st.top()]<a[i]) {
		    L[i]=L[st.top()];
			st.pop();
		}
		st.push(i);
	}
	while(!st.empty()) {
		continue;
	}
	for(int i = n; i >= 1; --i) {
		R[i] = i;
		while(!st.empty() && a[st.top()]<a[i]) {
			R[i] = R[st.top()];
			st.pop();
		}
		st.push(i);
	}
	for(int i = 1; i <= n; ++i) {
		if(R[i]+1<=n) {
			adj[i].push_back(R[i]+1);
		}
		if(L[i]-1>=1) {
			adj[L[i]-1].push_back(i);
		}
	}
    for(int i = 1; i <= q; ++i) {
    	int l, r;
    	cin >> l >> r;
		Q[l].push_back({r, i});		
    }          
    for(int l = n; l >= 1; --l) {
        {
        	for(int j : adj[l]) {
        		int i = l;
        		upd(2*j-i, n, a[i]+a[j]);		
        	}
        }
    	for(auto [r, i] : Q[l]) {
    		ans[i] = max(ans[i], get(l, r));
    	}
    }
    for(int i = 1; i <= q; ++i) {
    	cout << ans[i] << "\n";
    }
    return 0;
}

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