Submission #620680

#	Time	Username	Problem	Language	Result	Execution time	Memory
620680		flappybird	Triple Jump (JOI19_jumps)	C++17	100 / 100	2667 ms	82404 KiB

jumps

#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];
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;
	vector<int> qv;
	for (i = 1; i <= Q; i++) {
		qv.push_back(i);
		cin >> a >> b;
		query[i] = pii(a, b);
	}
	sort(qv.begin(), qv.end(), [&](int i, int j) { return query[i].first < query[j].first; });
	set<pii> vpi;
	vpi.emplace(0, 0);
	vpi.emplace(N + 1, INF);
	int ptr = Q - 1;
	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);
		}
		while (ptr >= 0 && query[qv[ptr]].first == i) ans[qv[ptr]] = seg.query(query[qv[ptr]].first, query[qv[ptr]].second), ptr--;
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54