제출 #201466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201466		maruii	3단 점프 (JOI19_jumps)	C++14	100 / 100	993 ms	88056 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int A[500005], N, Q, stk[500005], stn;
const int SIZE = 1 << 19;
struct ST {
	struct Node {
		unsigned a, b, v;
	} X[2 * SIZE];
	void init(int nn, int s, int e) {
		if (s == e) {
			X[nn].a = A[s];
			return;
		}
		int m = s + e >> 1;
		init(nn << 1, s, m);
		init(nn << 1 | 1, m + 1, e);
		X[nn].a = max(X[nn << 1].a, X[nn << 1 | 1].a);
	}
	void busy(int nn) {
		if (X[nn << 1].b < X[nn].b) {
			X[nn << 1].b = X[nn].b;
			X[nn << 1].v = max(X[nn << 1].v, X[nn << 1].a + X[nn].b);
		}
		if (X[nn << 1 | 1].b < X[nn].b) {
			X[nn << 1 | 1].b = X[nn].b;
			X[nn << 1 | 1].v = max(X[nn << 1 | 1].v, X[nn << 1 | 1].a + X[nn].b);
		}
	}
	void update(int nn, int ns, int ne, int s, int e, unsigned v) {
		if (ns > e || ne < s) return;
		if (s <= ns && ne <= e) {
			if (X[nn].b < v) {
				X[nn].b = v;
				X[nn].v = max(X[nn].v, X[nn].a + v);
			}
			return;
		}
		int m = ns + ne >> 1;
		busy(nn);
		update(nn << 1, ns, m, s, e, v);
		update(nn << 1 | 1, m + 1, ne, s, e, v);
		X[nn].v = max(X[nn << 1].v, X[nn << 1 | 1].v);
	}
	unsigned query(int nn, int ns, int ne, int s, int e) {
		if (ns > e || ne < s) return 0;
		if (s <= ns && ne <= e) return X[nn].v;
		int m = ns + ne >> 1;
		busy(nn);
		return max(query(nn << 1, ns, m, s, e), query(nn << 1 | 1, m + 1, ne, s, e));
	}
} seg;
vector<pair<int, int>> qry[500005];
vector<int> can[500005];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	seg.init(1, 1, N);
	for (int i = 1; i <= N; ++i) {
		while (stn && A[stk[stn - 1]] < A[i]) {
			--stn;
			can[stk[stn]].push_back(i);
		}
		if (stn) can[stk[stn - 1]].push_back(i);
		if (stn && A[i] == A[stk[stn - 1]]) stn--;
		stk[stn++] = i;
	}
	cin >> Q;
	vector<unsigned> ans(Q);
	for (int i = 0; i < Q; ++i) {
		int x, y; cin >> x >> y;
		qry[x].emplace_back(y, i);
	}
	for (int i = N; i; --i) {
		for (auto j : can[i]) seg.update(1, 1, N, j + j - i, N, A[i] + A[j]);
		for (auto j : qry[i]) ans[j.ss] = seg.query(1, 1, N, i, j.ff);
	}
	for (auto i : ans) printf("%u\n", i);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In member function 'void ST::init(int, int, int)':
jumps.cpp:18:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
jumps.cpp: In member function 'void ST::update(int, int, int, int, int, unsigned int)':
jumps.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
jumps.cpp: In member function 'unsigned int ST::query(int, int, int, int, int)':
jumps.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~

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