Submission #203859

#	Time	Username	Problem	Language	Result	Execution time	Memory
203859		youngyojun	Triple Jump (JOI19_jumps)	C++11	100 / 100	1127 ms	99704 KiB

jumps

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 500055;
const int MAXQ = 500055;

struct NOD {
	NOD(int a = 0, int b = 0, int c = 0)
		: a(a), b(b), c(c) {}
	int a, b, c;

	NOD operator + (const NOD &t) const {
		return NOD(max(a, t.a), max(b, t.b), max({c, t.c, b + t.a}));
	}
};

struct SEG {
	NOD nod[MAXN*3];

	void init(int i, int s, int e, int A[]) {
		if(s == e) {
			nod[i].a = A[s];
			nod[i].b = nod[i].c = -INF;
			return;
		}
		int m = s+e >> 1;
		init(i<<1, s, m, A);
		init(i<<1|1, m+1, e, A);
		nod[i] = nod[i<<1] + nod[i<<1|1];
	}

	void upd(int i, int s, int e, int x, int r) {
		if(x < s || e < x) return;
		if(s == e) {
			upmax(nod[i].b, r);
			nod[i].c = nod[i].a + nod[i].b;
			return;
		}
		int m = s+e >> 1;
		if(x <= m) upd(i<<1, s, m, x, r);
		else upd(i<<1|1, m+1, e, x, r);
		nod[i] = nod[i<<1] + nod[i<<1|1];
	}
	NOD get(int i, int s, int e, int p, int q) {
		if(e < s || q < p || e < p || q < s) return NOD();
		if(p <= s && e <= q) return nod[i];
		int m = s+e >> 1;
		return get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
	}
} seg;

vector<pii> TV[MAXN];
vector<int> QV[MAXN];

int A[MAXN];
int B[MAXQ], C[MAXQ];

int Ans[MAXQ];
int N, Q;

void precal() {
	vector<pii> V = {{0, INF}};
	for(int i = 1; i <= N; i++) {
		for(int t; 1 < sz(V); V.pop_back()) {
			t = i*2 - V.back().fi;
			if(t <= N) TV[V.back().fi].eb(t, V.back().se + A[i]);
			if(A[i] < V.back().se) break;
		}
		V.eb(i, A[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	cin >> Q;
	for(int i = 1; i <= Q; i++) {
		cin >> B[i] >> C[i];
		QV[B[i]].eb(i);
	}

	precal();
	seg.init(1, 1, N, A);

	for(int i = N; i; i--) {
		for(auto &v : TV[i]) seg.upd(1, 1, N, v.fi, v.se);
		for(int j : QV[i]) Ans[j] = seg.get(1, 1, N, B[j], C[j]).c;
	}

	for(int i = 1; i <= Q; i++)
		cout << Ans[i] << '\n';
	return 0;
}

Compilation message (stderr)

jumps.cpp: In member function 'void SEG::init(int, int, int, int*)':
jumps.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
jumps.cpp: In member function 'void SEG::upd(int, int, int, int, int)':
jumps.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
jumps.cpp: In member function 'NOD SEG::get(int, int, int, int, int)':
jumps.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~

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