Submission #620534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
620534	2022-08-03T06:49:32 Z	flappybird	Triple Jump (JOI19_jumps)	C++17	46 / 100	4000 ms	76304 KB

jumps

#include <bits/stdc++.h>
#pragma GCC optimize("O0")
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	16 ms	24020 KB	Output is correct
2	Correct	13 ms	24020 KB	Output is correct
3	Correct	19 ms	24044 KB	Output is correct
4	Correct	14 ms	24060 KB	Output is correct
5	Correct	20 ms	24068 KB	Output is correct
6	Correct	16 ms	24012 KB	Output is correct
7	Correct	14 ms	23988 KB	Output is correct
8	Correct	14 ms	24020 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	13 ms	24068 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	24020 KB	Output is correct
2	Correct	13 ms	24020 KB	Output is correct
3	Correct	19 ms	24044 KB	Output is correct
4	Correct	14 ms	24060 KB	Output is correct
5	Correct	20 ms	24068 KB	Output is correct
6	Correct	16 ms	24012 KB	Output is correct
7	Correct	14 ms	23988 KB	Output is correct
8	Correct	14 ms	24020 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	13 ms	24068 KB	Output is correct
11	Correct	1157 ms	42472 KB	Output is correct
12	Correct	1140 ms	42336 KB	Output is correct
13	Correct	1175 ms	42444 KB	Output is correct
14	Correct	1149 ms	42396 KB	Output is correct
15	Correct	1189 ms	42468 KB	Output is correct
16	Correct	1155 ms	41936 KB	Output is correct
17	Correct	1207 ms	41712 KB	Output is correct
18	Correct	1213 ms	41696 KB	Output is correct
19	Correct	1268 ms	42324 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1057 ms	41292 KB	Output is correct
2	Correct	407 ms	50424 KB	Output is correct
3	Correct	1224 ms	41888 KB	Output is correct
4	Correct	1083 ms	41296 KB	Output is correct
5	Correct	1035 ms	41288 KB	Output is correct
6	Correct	1079 ms	40640 KB	Output is correct
7	Correct	1068 ms	40544 KB	Output is correct
8	Correct	1054 ms	40536 KB	Output is correct
9	Correct	1111 ms	41000 KB	Output is correct

Subtask #4

0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	24020 KB	Output is correct
2	Correct	13 ms	24020 KB	Output is correct
3	Correct	19 ms	24044 KB	Output is correct
4	Correct	14 ms	24060 KB	Output is correct
5	Correct	20 ms	24068 KB	Output is correct
6	Correct	16 ms	24012 KB	Output is correct
7	Correct	14 ms	23988 KB	Output is correct
8	Correct	14 ms	24020 KB	Output is correct
9	Correct	15 ms	24020 KB	Output is correct
10	Correct	13 ms	24068 KB	Output is correct
11	Correct	1157 ms	42472 KB	Output is correct
12	Correct	1140 ms	42336 KB	Output is correct
13	Correct	1175 ms	42444 KB	Output is correct
14	Correct	1149 ms	42396 KB	Output is correct
15	Correct	1189 ms	42468 KB	Output is correct
16	Correct	1155 ms	41936 KB	Output is correct
17	Correct	1207 ms	41712 KB	Output is correct
18	Correct	1213 ms	41696 KB	Output is correct
19	Correct	1268 ms	42324 KB	Output is correct
20	Correct	1057 ms	41292 KB	Output is correct
21	Correct	407 ms	50424 KB	Output is correct
22	Correct	1224 ms	41888 KB	Output is correct
23	Correct	1083 ms	41296 KB	Output is correct
24	Correct	1035 ms	41288 KB	Output is correct
25	Correct	1079 ms	40640 KB	Output is correct
26	Correct	1068 ms	40544 KB	Output is correct
27	Correct	1054 ms	40536 KB	Output is correct
28	Correct	1111 ms	41000 KB	Output is correct
29	Execution timed out	4011 ms	76304 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-