oj.uz

Submission #256168

# Submission time Handle Problem Language Result Execution time Memory
256168 2020-08-02T10:46:29 Z Atalasion Triple Jump (JOI19_jumps) C++14
100 / 100
 1202 ms 86184 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

struct node{
	int mx, num, ans;
};

struct query{
	int id, R;
};

int n, m, a[N], lazy[N << 2], ans[N];
node seg[N << 2];
vector<query> L[N];

node merge(node x, node y){
	node res = x;
	res.mx = max(res.mx, y.mx);
	res.num = max(res.num, y.num);
	res.ans = max(res.ans, y.ans);
	return res;
}

void modify(int id, int x){
	seg[id].mx = x;
	seg[id].ans = seg[id].mx + seg[id].num;
	lazy[id] = x;
}

void shift(int id){
	if (lazy[id] == -1) return;
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = -1;
}

void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].mx = seg[id].ans = 0;
		seg[id].num = a[l];
		return;
	}
	int md = (l + r) >> 1;
	build(id << 1, l, md);
	build(id << 1 | 1, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

int BS(int id, int x, int l, int r){
	if (r - l == 1){
//		cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
		if (seg[id].mx < x) return n + 1;
		return l;
	}
	shift(id);
	int md = (l + r) >> 1;
	if (seg[id << 1].mx >= x) return BS(id << 1, x, l, md);
	return BS(id << 1 | 1, x, md, r);
}

void Set(int id, int lq, int rq, int x, int l, int r){
	if (rq <= lq) return;
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		modify(id, x);
//		cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
		return;
	}
	int md = (l + r) >> 1;
	shift(id);
	Set(id << 1, lq, rq, x, l, md);
	Set(id << 1 | 1, lq, rq, x, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

int get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		return seg[id].ans;
	}
	shift(id);
	int md = (l + r) >> 1;
	return max(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++){
		int l, r;
		cin >> l >> r;
		query res;
		res.id = i, res.R = r;
		L[l].pb(res);
	}
	build(1, 1, n + 1);
//	cout << "YES" << endl;
	stack<int> st;
	st.push(n);
	for (int i = n - 1; i >= 1; i--){
//		cout << i << endl;
		while (st.size() && a[st.top()] <= a[i]){
			int sm = a[i] + a[st.top()];
			int l = i, r = st.top();
			int R = 2 * r - l;
			if (R <= n){
//				cout << "YES" << endl;
				int koj = BS(1, sm, 1, n + 1);
//				cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
				Set(1, R, koj, sm, 1, n + 1);
//				cout << "YES2" << endl;
			}
			st.pop();
			
		}
//		cout << "YES2" << endl;
		if (st.size()){
			int sm = a[i] + a[st.top()];
			int l = i, r = st.top();
			int R = 2 * r - l;
			if (R <= n){
				int koj = BS(1, sm, 1, n + 1);
//				cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
				Set(1, R, koj, sm, 1, n + 1);
			}
		}
		st.push(i);
		for (auto u:L[i]) ans[u.id] = get(1, i, u.R + 1, 1, n + 1);
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';








	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 7 ms 12160 KB Output is correct
4 Correct 7 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 7 ms 12160 KB Output is correct
7 Correct 7 ms 12160 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 7 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 266 ms 38904 KB Output is correct
12 Correct 269 ms 38904 KB Output is correct
13 Correct 278 ms 39032 KB Output is correct
14 Correct 271 ms 38904 KB Output is correct
15 Correct 293 ms 39008 KB Output is correct
16 Correct 275 ms 38392 KB Output is correct
17 Correct 294 ms 38264 KB Output is correct
18 Correct 259 ms 38136 KB Output is correct
19 Correct 316 ms 38848 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 31864 KB Output is correct
2 Correct 96 ms 33528 KB Output is correct
3 Correct 104 ms 31864 KB Output is correct
4 Correct 139 ms 31908 KB Output is correct
5 Correct 144 ms 31864 KB Output is correct
6 Correct 128 ms 31224 KB Output is correct
7 Correct 130 ms 31096 KB Output is correct
8 Correct 132 ms 31096 KB Output is correct
9 Correct 130 ms 31480 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 7 ms 12160 KB Output is correct
4 Correct 7 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 7 ms 12160 KB Output is correct
7 Correct 7 ms 12160 KB Output is correct
8 Correct 7 ms 12160 KB Output is correct
9 Correct 7 ms 12160 KB Output is correct
10 Correct 8 ms 12160 KB Output is correct
11 Correct 266 ms 38904 KB Output is correct
12 Correct 269 ms 38904 KB Output is correct
13 Correct 278 ms 39032 KB Output is correct
14 Correct 271 ms 38904 KB Output is correct
15 Correct 293 ms 39008 KB Output is correct
16 Correct 275 ms 38392 KB Output is correct
17 Correct 294 ms 38264 KB Output is correct
18 Correct 259 ms 38136 KB Output is correct
19 Correct 316 ms 38848 KB Output is correct
20 Correct 140 ms 31864 KB Output is correct
21 Correct 96 ms 33528 KB Output is correct
22 Correct 104 ms 31864 KB Output is correct
23 Correct 139 ms 31908 KB Output is correct
24 Correct 144 ms 31864 KB Output is correct
25 Correct 128 ms 31224 KB Output is correct
26 Correct 130 ms 31096 KB Output is correct
27 Correct 132 ms 31096 KB Output is correct
28 Correct 130 ms 31480 KB Output is correct
29 Correct 1062 ms 82040 KB Output is correct
30 Correct 884 ms 86184 KB Output is correct
31 Correct 882 ms 81864 KB Output is correct
32 Correct 1202 ms 81916 KB Output is correct
33 Correct 1089 ms 82040 KB Output is correct
34 Correct 936 ms 79480 KB Output is correct
35 Correct 955 ms 79328 KB Output is correct
36 Correct 937 ms 79352 KB Output is correct
37 Correct 941 ms 80888 KB Output is correct
38 Correct 660 ms 84420 KB Output is correct
39 Correct 662 ms 84480 KB Output is correct
40 Correct 650 ms 81204 KB Output is correct
41 Correct 622 ms 80632 KB Output is correct
42 Correct 643 ms 80632 KB Output is correct
43 Correct 654 ms 82296 KB Output is correct
44 Correct 710 ms 84880 KB Output is correct
45 Correct 717 ms 84728 KB Output is correct
46 Correct 664 ms 81660 KB Output is correct
47 Correct 654 ms 81272 KB Output is correct
48 Correct 664 ms 81316 KB Output is correct
49 Correct 680 ms 83428 KB Output is correct
50 Correct 763 ms 85204 KB Output is correct
51 Correct 757 ms 85112 KB Output is correct
52 Correct 724 ms 82600 KB Output is correct
53 Correct 746 ms 82176 KB Output is correct
54 Correct 784 ms 82168 KB Output is correct
55 Correct 809 ms 83844 KB Output is correct