oj.uz

Submission #620520

# Submission time Handle Problem Language Result Execution time Memory
620520 2022-08-03T06:44:22 Z flappybird Triple Jump (JOI19_jumps) C++17
100 / 100
 2617 ms 101364 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);
	}
	inline void prop(int x) {
		if (!x) return;
		if (x >= s) return;
		for (auto c : { 2 * x, 2 * x + 1 }) {
			tree[c] += lazy[x];
			lazy[c] += lazy[x];
		}
		lazy[x] = 0;
	}
	inline 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]);
		}
	}
	inline 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 13 ms 24020 KB Output is correct
2 Correct 17 ms 24076 KB Output is correct
3 Correct 13 ms 24084 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 24072 KB Output is correct
6 Correct 11 ms 24020 KB Output is correct
7 Correct 11 ms 24072 KB Output is correct
8 Correct 15 ms 23980 KB Output is correct
9 Correct 17 ms 24020 KB Output is correct
10 Correct 13 ms 24084 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24020 KB Output is correct
2 Correct 17 ms 24076 KB Output is correct
3 Correct 13 ms 24084 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 24072 KB Output is correct
6 Correct 11 ms 24020 KB Output is correct
7 Correct 11 ms 24072 KB Output is correct
8 Correct 15 ms 23980 KB Output is correct
9 Correct 17 ms 24020 KB Output is correct
10 Correct 13 ms 24084 KB Output is correct
11 Correct 678 ms 38868 KB Output is correct
12 Correct 590 ms 38748 KB Output is correct
13 Correct 584 ms 38880 KB Output is correct
14 Correct 585 ms 38880 KB Output is correct
15 Correct 638 ms 38876 KB Output is correct
16 Correct 611 ms 38184 KB Output is correct
17 Correct 642 ms 38128 KB Output is correct
18 Correct 593 ms 38112 KB Output is correct
19 Correct 598 ms 38744 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 39556 KB Output is correct
2 Correct 246 ms 48656 KB Output is correct
3 Correct 551 ms 40156 KB Output is correct
4 Correct 569 ms 39552 KB Output is correct
5 Correct 527 ms 39552 KB Output is correct
6 Correct 523 ms 39552 KB Output is correct
7 Correct 533 ms 39552 KB Output is correct
8 Correct 547 ms 39556 KB Output is correct
9 Correct 517 ms 39560 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24020 KB Output is correct
2 Correct 17 ms 24076 KB Output is correct
3 Correct 13 ms 24084 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 24072 KB Output is correct
6 Correct 11 ms 24020 KB Output is correct
7 Correct 11 ms 24072 KB Output is correct
8 Correct 15 ms 23980 KB Output is correct
9 Correct 17 ms 24020 KB Output is correct
10 Correct 13 ms 24084 KB Output is correct
11 Correct 678 ms 38868 KB Output is correct
12 Correct 590 ms 38748 KB Output is correct
13 Correct 584 ms 38880 KB Output is correct
14 Correct 585 ms 38880 KB Output is correct
15 Correct 638 ms 38876 KB Output is correct
16 Correct 611 ms 38184 KB Output is correct
17 Correct 642 ms 38128 KB Output is correct
18 Correct 593 ms 38112 KB Output is correct
19 Correct 598 ms 38744 KB Output is correct
20 Correct 733 ms 39556 KB Output is correct
21 Correct 246 ms 48656 KB Output is correct
22 Correct 551 ms 40156 KB Output is correct
23 Correct 569 ms 39552 KB Output is correct
24 Correct 527 ms 39552 KB Output is correct
25 Correct 523 ms 39552 KB Output is correct
26 Correct 533 ms 39552 KB Output is correct
27 Correct 547 ms 39556 KB Output is correct
28 Correct 517 ms 39560 KB Output is correct
29 Correct 2372 ms 78476 KB Output is correct
30 Correct 1754 ms 101364 KB Output is correct
31 Correct 2573 ms 79884 KB Output is correct
32 Correct 2466 ms 78476 KB Output is correct
33 Correct 2431 ms 78488 KB Output is correct
34 Correct 2320 ms 77844 KB Output is correct
35 Correct 2430 ms 77728 KB Output is correct
36 Correct 2579 ms 77724 KB Output is correct
37 Correct 2617 ms 78368 KB Output is correct
38 Correct 2137 ms 85060 KB Output is correct
39 Correct 1980 ms 85060 KB Output is correct
40 Correct 1960 ms 83424 KB Output is correct
41 Correct 1995 ms 83172 KB Output is correct
42 Correct 2029 ms 83272 KB Output is correct
43 Correct 1993 ms 84044 KB Output is correct
44 Correct 2115 ms 84472 KB Output is correct
45 Correct 2261 ms 84372 KB Output is correct
46 Correct 2083 ms 82992 KB Output is correct
47 Correct 2176 ms 82800 KB Output is correct
48 Correct 2149 ms 82832 KB Output is correct
49 Correct 2174 ms 84056 KB Output is correct
50 Correct 2286 ms 82088 KB Output is correct
51 Correct 2240 ms 82160 KB Output is correct
52 Correct 2272 ms 81328 KB Output is correct
53 Correct 2363 ms 81236 KB Output is correct
54 Correct 2378 ms 81224 KB Output is correct
55 Correct 2280 ms 82084 KB Output is correct