oj.uz

Submission #981024

# Submission time Handle Problem Language Result Execution time Memory
981024 2024-05-12T17:49:27 Z NintsiChkhaidze Triple Jump (JOI19_jumps) C++17
100 / 100
 1463 ms 112068 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] >= a[st.back()]){
			pr[st.back()].pb(i);
			st.pop_back();
		}

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

	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 7 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 7 ms 31320 KB Output is correct
10 Correct 7 ms 31320 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 7 ms 31320 KB Output is correct
10 Correct 7 ms 31320 KB Output is correct
11 Correct 796 ms 53896 KB Output is correct
12 Correct 744 ms 53684 KB Output is correct
13 Correct 761 ms 53908 KB Output is correct
14 Correct 765 ms 53844 KB Output is correct
15 Correct 751 ms 53876 KB Output is correct
16 Correct 735 ms 53164 KB Output is correct
17 Correct 745 ms 53260 KB Output is correct
18 Correct 786 ms 52988 KB Output is correct
19 Correct 753 ms 53540 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 53196 KB Output is correct
2 Correct 62 ms 53584 KB Output is correct
3 Correct 64 ms 55068 KB Output is correct
4 Correct 117 ms 54864 KB Output is correct
5 Correct 122 ms 54740 KB Output is correct
6 Correct 109 ms 54088 KB Output is correct
7 Correct 110 ms 54120 KB Output is correct
8 Correct 113 ms 54184 KB Output is correct
9 Correct 121 ms 54284 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31320 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 7 ms 31320 KB Output is correct
10 Correct 7 ms 31320 KB Output is correct
11 Correct 796 ms 53896 KB Output is correct
12 Correct 744 ms 53684 KB Output is correct
13 Correct 761 ms 53908 KB Output is correct
14 Correct 765 ms 53844 KB Output is correct
15 Correct 751 ms 53876 KB Output is correct
16 Correct 735 ms 53164 KB Output is correct
17 Correct 745 ms 53260 KB Output is correct
18 Correct 786 ms 52988 KB Output is correct
19 Correct 753 ms 53540 KB Output is correct
20 Correct 134 ms 53196 KB Output is correct
21 Correct 62 ms 53584 KB Output is correct
22 Correct 64 ms 55068 KB Output is correct
23 Correct 117 ms 54864 KB Output is correct
24 Correct 122 ms 54740 KB Output is correct
25 Correct 109 ms 54088 KB Output is correct
26 Correct 110 ms 54120 KB Output is correct
27 Correct 113 ms 54184 KB Output is correct
28 Correct 121 ms 54284 KB Output is correct
29 Correct 1463 ms 109492 KB Output is correct
30 Correct 1289 ms 106364 KB Output is correct
31 Correct 1325 ms 110184 KB Output is correct
32 Correct 1423 ms 109828 KB Output is correct
33 Correct 1412 ms 109360 KB Output is correct
34 Correct 1372 ms 107288 KB Output is correct
35 Correct 1410 ms 106908 KB Output is correct
36 Correct 1351 ms 107184 KB Output is correct
37 Correct 1339 ms 108216 KB Output is correct
38 Correct 1063 ms 111852 KB Output is correct
39 Correct 1053 ms 112068 KB Output is correct
40 Correct 1074 ms 108904 KB Output is correct
41 Correct 1046 ms 108508 KB Output is correct
42 Correct 1057 ms 108120 KB Output is correct
43 Correct 1060 ms 109984 KB Output is correct
44 Correct 1096 ms 111620 KB Output is correct
45 Correct 1104 ms 111744 KB Output is correct
46 Correct 1092 ms 108656 KB Output is correct
47 Correct 1084 ms 108464 KB Output is correct
48 Correct 1135 ms 108268 KB Output is correct
49 Correct 1117 ms 110172 KB Output is correct
50 Correct 1170 ms 111148 KB Output is correct
51 Correct 1171 ms 111072 KB Output is correct
52 Correct 1159 ms 108436 KB Output is correct
53 Correct 1167 ms 108100 KB Output is correct
54 Correct 1172 ms 108240 KB Output is correct
55 Correct 1178 ms 110324 KB Output is correct