Submission #950857

#	Time	Username	Problem	Language	Result	Execution time	Memory
950857		pragmatist	Triple Jump (JOI19_jumps)	C++17	100 / 100	919 ms	96340 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];

int add[4*N], t[4*N], mx[4*N];

void build(int v, int tl, int tr) {
	if(tl == tr) {
		t[v] = a[tl];
		return;
	}
	int mid = (tl+tr)/2;
	build(v*2, tl, mid);
	build(v*2+1, mid+1, tr);
	t[v] = max(t[v*2], t[v*2+1]);
	mx[v] = t[v];
}

void push(int v, int tl, int tr) {
	if(tl != tr) {
		add[v*2] = max(add[v*2], add[v]);
		add[v*2+1] = max(add[v*2+1], add[v]);
	}
	mx[v] = max(mx[v], t[v]+add[v]);
}

void upd(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if(tl>r || l>tr) {
		return;
	}
	if(tl >= l && tr<= r) {
		add[v] = max(add[v], x);
		push(v, tl, tr);
		return;
	}
	int mid = (tl+tr)>>1;
	upd(v*2, tl, mid, l, r, x);
	upd(v*2+1, mid+1, tr, l, r, x);
	mx[v] = max(mx[v*2], mx[v*2+1]);
}

void upd(int l, int r, int x) {
	if(l>r) {
		return;
	}
	upd(1, 1, n, l, r, x);
}

int get(int v, int tl, int tr, int l, int r) {
	push(v, tl, tr);
	if(tl >= l && tr <= r) {
		return mx[v];	
	}
	if(tl>r || l > tr) {
		return 0;
	}
	int mid = (tl+tr)/2;
	return max(get(v*2, tl, mid, l, r), get(v*2+1, mid+1, tr, l, r));
}

int get(int l, int r) {
    if(l>r) {
    	return 0;
    }
	return get(1, 1, n, l, r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	} 
	build(1, 1, n);
	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: 27 / 27
• Subtask 4: 54 / 54