oj.uz

Submission #950601

# Submission time Handle Problem Language Result Execution time Memory
950601 2024-03-20T13:32:26 Z pragmatist Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 43564 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 7 ms 29528 KB Output is correct
5 Correct 7 ms 29384 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29272 KB Output is correct
9 Correct 7 ms 29528 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 7 ms 29528 KB Output is correct
5 Correct 7 ms 29384 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29272 KB Output is correct
9 Correct 7 ms 29528 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 906 ms 43564 KB Output is correct
12 Correct 886 ms 43200 KB Output is correct
13 Correct 885 ms 43340 KB Output is correct
14 Correct 910 ms 43504 KB Output is correct
15 Correct 898 ms 43320 KB Output is correct
16 Correct 890 ms 42836 KB Output is correct
17 Correct 913 ms 42580 KB Output is correct
18 Correct 896 ms 42764 KB Output is correct
19 Correct 889 ms 43248 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 36384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 7 ms 29276 KB Output is correct
4 Correct 7 ms 29528 KB Output is correct
5 Correct 7 ms 29384 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29272 KB Output is correct
9 Correct 7 ms 29528 KB Output is correct
10 Correct 6 ms 29276 KB Output is correct
11 Correct 906 ms 43564 KB Output is correct
12 Correct 886 ms 43200 KB Output is correct
13 Correct 885 ms 43340 KB Output is correct
14 Correct 910 ms 43504 KB Output is correct
15 Correct 898 ms 43320 KB Output is correct
16 Correct 890 ms 42836 KB Output is correct
17 Correct 913 ms 42580 KB Output is correct
18 Correct 896 ms 42764 KB Output is correct
19 Correct 889 ms 43248 KB Output is correct
20 Execution timed out 4035 ms 36384 KB Time limit exceeded
21 Halted 0 ms 0 KB -