oj.uz

Submission #981019

# Submission time Handle Problem Language Result Execution time Memory
981019 2024-05-12T17:45:26 Z NintsiChkhaidze Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 58552 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
// #pragma GCC optimize("Ofast")
using namespace std;
 
const int N = 5e5 + 3;
vector <pii> qr[N];
vector <int> pr[N];
int a[N],told[4*N],tnew[4*N],lz[4*N];
int ans[N];

void build(int h,int l,int r){
	if (l == r){
		told[h] = tnew[h] = a[l];
		return;
	}

	build(left);
	build(right);
	told[h] = tnew[h] = max(told[h*2],told[h*2+1]);
}

void push(int h){
	if (lz[h]==0) return;
	lz[h*2]=max(lz[h*2],lz[h]);
	lz[h*2+1] = max(lz[h*2+1],lz[h]);
	tnew[h*2] = max(tnew[h*2],told[h*2] + lz[h]);
	tnew[h*2+1] = max(tnew[h*2+1],told[h*2+1] + lz[h]);
	lz[h]=0;
}

void upd(int h,int l,int r,int L,int R,int val){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		tnew[h] = max(tnew[h],val + told[h]);
		lz[h] = max(lz[h],val);
		return;
	}

	push(h);
	upd(left,L,R,val);
	upd(right,L,R,val);
	tnew[h] = max(tnew[h*2],tnew[h*2+1]);
}

int get(int h,int l,int r,int L,int R){
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return tnew[h];
	push(h);
	return max(get(left,L,R),get(right,L,R));
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n;

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	build(1,1,n);
	int q;
	cin>>q;

	for (int i = 1; i <= q; i++){
		int l,r;
		cin>>l>>r;
		qr[l].pb({r,i});
	}

	// vector <int> st;
	// for (int i = 1; i <= n; i++){
	// 	while (st.size() && a[i] >= st.back()){
	// 		pr[st.back()].pb(i);
	// 		st.pop_back();
	// 	}

	// 	if (st.size()) pr[st.back()].pb(i);
	// 	st.pb(i);
	// }

	//neli
	for (int i = 1; i <= n; i++){
		int mx = 0;
		for (int j = i + 1; j <= n; j++){
			if (j > i && mx < a[j] && mx < a[i]) {
				pr[i].pb(j);
			}

			mx=max(mx,a[j]);
		}
	}

	for (int i = n; i >= 1; i--){
		for (int j: pr[i]){
			int l = 2*j - i,r = n;
			upd(1,1,n,l,r,a[i] + a[j]);
		}

		for (auto c: qr[i]){
			ans[c.s] = get(1,1,n,i,c.f);
		}
	}

	for (int i = 1; i <= q; i++)
		cout<<ans[i]<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31320 KB Output is correct
2 Correct 8 ms 31324 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31304 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31320 KB Output is correct
2 Correct 8 ms 31324 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31304 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 770 ms 58552 KB Output is correct
12 Correct 768 ms 58416 KB Output is correct
13 Correct 784 ms 58496 KB Output is correct
14 Correct 785 ms 58408 KB Output is correct
15 Correct 770 ms 58452 KB Output is correct
16 Correct 800 ms 58020 KB Output is correct
17 Correct 770 ms 57720 KB Output is correct
18 Correct 765 ms 57932 KB Output is correct
19 Correct 766 ms 58252 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 42092 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 31320 KB Output is correct
2 Correct 8 ms 31324 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31304 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 7 ms 31324 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 770 ms 58552 KB Output is correct
12 Correct 768 ms 58416 KB Output is correct
13 Correct 784 ms 58496 KB Output is correct
14 Correct 785 ms 58408 KB Output is correct
15 Correct 770 ms 58452 KB Output is correct
16 Correct 800 ms 58020 KB Output is correct
17 Correct 770 ms 57720 KB Output is correct
18 Correct 765 ms 57932 KB Output is correct
19 Correct 766 ms 58252 KB Output is correct
20 Execution timed out 4067 ms 42092 KB Time limit exceeded
21 Halted 0 ms 0 KB -