oj.uz

Submission #620437

# Submission time Handle Problem Language Result Execution time Memory
620437 2022-08-03T05:57:53 Z flappybird Triple Jump (JOI19_jumps) C++17
100 / 100
 2414 ms 112368 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 505050
#define MAXS 20
#define INF 1e9
#define bb ' '
#define ln '\n'
#define Ln '\n'
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
#define MOD 1000000007
struct segtree {
	int s;
	vector<int> tree, lazy, l, r;
	void init(int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		tree[x] = max(tree[x + 1], tree[x * 2 + 1]);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
	}
	segtree() {}
	segtree(int N) {
		s = 1 << (int)ceil(log2(N));
		tree = lazy = l = r = vector<int>(2 * s + 1);
	}
	void prop(int x) {
		if (x >= s) return;
		for (auto c : { 2 * x, 2 * x + 1 }) {
			tree[c] += lazy[x];
			lazy[c] += lazy[x];
		}
		lazy[x] = 0;
	}
	void update(int low, int high, int x, int loc = 1) {
		prop(loc);
		if (low == l[loc] && high == r[loc]) {
			tree[loc] += x;
			lazy[loc] += x;
		}
		else {
			if (high <= r[loc * 2]) update(low, high, x, loc * 2);
			else if (low >= l[loc * 2 + 1]) update(low, high, x, loc * 2 + 1);
			else update(low, r[loc * 2], x, loc * 2), update(l[loc * 2 + 1], high, x, loc * 2 + 1);
			tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
		}
	}
	int query(int low, int high, int loc = 1) {
		prop(loc);
		if (low == l[loc] && high == r[loc]) return tree[loc];
		if (high <= r[loc * 2]) return query(low, high, loc * 2);
		if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
		return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
};
int A[MAX];
pii query[MAX];
vector<int> st[MAX], qst[MAX];
int ans[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	stack<int> s;
	segtree seg(N);
	for (i = 1; i <= N; i++) cin >> A[i], seg.tree[i + seg.s - 1] = A[i];
	seg.init();
	for (i = 1; i <= N; i++) {
		while (s.size()) {
			st[s.top()].push_back(i);
			if (A[s.top()] > A[i]) break;
			else s.pop();
		}
		s.push(i);
	}
	int Q;
	cin >> Q;
	int a, b;
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		query[i] = pii(a, b);
		qst[a].push_back(i);
	}
	set<pii> vpi;
	vpi.emplace(0, 0);
	vpi.emplace(N + 1, INF);
	for (i = N; i >= 1; i--) {
		for (auto v : st[i]) {
			int e = 2 * v - i;
			if (e > N) continue;
			int X = A[i] + A[v];
			auto it = vpi.upper_bound(pii(e, INF));
			it--;
			if (it->second > X) continue;
			if (it->first == e) {
				auto pv = prev(it);
				int xx = it->second;
				int r = next(it)->first;
				seg.update(e, r - 1, pv->second - xx);
				vpi.erase(it);
				it = pv;
			}
			int p = it->second;
			auto it2 = next(it);
			vector<pii> er;
			for (; it2 != vpi.end(); it2++) {
				if (it2->second > X) break;
				auto it3 = next(it2);
				seg.update(it2->first, it3->first - 1, p - it2->second);
				er.push_back(*it2);
			}
			for (auto v : er) vpi.erase(v);
			it2 = next(it);
			seg.update(e, it2->first - 1, X - it->second);
			vpi.emplace(e, X);
		}
		for (auto q : qst[i]) ans[q] = seg.query(query[q].first, query[q].second);
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 12 ms 24072 KB Output is correct
3 Correct 12 ms 24020 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 11 ms 23964 KB Output is correct
6 Correct 13 ms 24192 KB Output is correct
7 Correct 12 ms 24072 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24068 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 12 ms 24072 KB Output is correct
3 Correct 12 ms 24020 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 11 ms 23964 KB Output is correct
6 Correct 13 ms 24192 KB Output is correct
7 Correct 12 ms 24072 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24068 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 539 ms 43592 KB Output is correct
12 Correct 550 ms 43472 KB Output is correct
13 Correct 560 ms 43516 KB Output is correct
14 Correct 530 ms 43564 KB Output is correct
15 Correct 535 ms 43600 KB Output is correct
16 Correct 530 ms 42964 KB Output is correct
17 Correct 519 ms 42832 KB Output is correct
18 Correct 517 ms 42816 KB Output is correct
19 Correct 564 ms 43452 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 39552 KB Output is correct
2 Correct 241 ms 48656 KB Output is correct
3 Correct 547 ms 40164 KB Output is correct
4 Correct 489 ms 39652 KB Output is correct
5 Correct 485 ms 39552 KB Output is correct
6 Correct 526 ms 39556 KB Output is correct
7 Correct 463 ms 39628 KB Output is correct
8 Correct 525 ms 39520 KB Output is correct
9 Correct 471 ms 39556 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 12 ms 24072 KB Output is correct
3 Correct 12 ms 24020 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 11 ms 23964 KB Output is correct
6 Correct 13 ms 24192 KB Output is correct
7 Correct 12 ms 24072 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 13 ms 24068 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 539 ms 43592 KB Output is correct
12 Correct 550 ms 43472 KB Output is correct
13 Correct 560 ms 43516 KB Output is correct
14 Correct 530 ms 43564 KB Output is correct
15 Correct 535 ms 43600 KB Output is correct
16 Correct 530 ms 42964 KB Output is correct
17 Correct 519 ms 42832 KB Output is correct
18 Correct 517 ms 42816 KB Output is correct
19 Correct 564 ms 43452 KB Output is correct
20 Correct 496 ms 39552 KB Output is correct
21 Correct 241 ms 48656 KB Output is correct
22 Correct 547 ms 40164 KB Output is correct
23 Correct 489 ms 39652 KB Output is correct
24 Correct 485 ms 39552 KB Output is correct
25 Correct 526 ms 39556 KB Output is correct
26 Correct 463 ms 39628 KB Output is correct
27 Correct 525 ms 39520 KB Output is correct
28 Correct 471 ms 39556 KB Output is correct
29 Correct 2255 ms 89472 KB Output is correct
30 Correct 1737 ms 112368 KB Output is correct
31 Correct 2406 ms 90844 KB Output is correct
32 Correct 2271 ms 89480 KB Output is correct
33 Correct 2414 ms 89464 KB Output is correct
34 Correct 2268 ms 87192 KB Output is correct
35 Correct 2238 ms 86864 KB Output is correct
36 Correct 2274 ms 86824 KB Output is correct
37 Correct 2296 ms 88292 KB Output is correct
38 Correct 1911 ms 96008 KB Output is correct
39 Correct 1893 ms 96044 KB Output is correct
40 Correct 1928 ms 92996 KB Output is correct
41 Correct 1971 ms 92264 KB Output is correct
42 Correct 2089 ms 92228 KB Output is correct
43 Correct 2072 ms 93980 KB Output is correct
44 Correct 2138 ms 95452 KB Output is correct
45 Correct 2017 ms 95440 KB Output is correct
46 Correct 2121 ms 92480 KB Output is correct
47 Correct 2111 ms 91912 KB Output is correct
48 Correct 2001 ms 91840 KB Output is correct
49 Correct 2048 ms 94060 KB Output is correct
50 Correct 2155 ms 93164 KB Output is correct
51 Correct 2166 ms 93236 KB Output is correct
52 Correct 2150 ms 90804 KB Output is correct
53 Correct 2082 ms 90412 KB Output is correct
54 Correct 2073 ms 90400 KB Output is correct
55 Correct 2116 ms 92228 KB Output is correct