oj.uz

Submission #201458

# Submission time Handle Problem Language Result Execution time Memory
201458 2020-02-10T15:48:50 Z maruii Triple Jump (JOI19_jumps) C++14
27 / 100
 155 ms 39632 KB 
#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[stk[stn - 1]] != A[i]) 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;
}

Compilation message

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct
3 Correct 19 ms 23928 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Incorrect 19 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct
3 Correct 19 ms 23928 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Incorrect 19 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 38952 KB Output is correct
2 Correct 99 ms 38776 KB Output is correct
3 Correct 95 ms 39632 KB Output is correct
4 Correct 155 ms 39180 KB Output is correct
5 Correct 148 ms 39008 KB Output is correct
6 Correct 145 ms 38264 KB Output is correct
7 Correct 147 ms 38396 KB Output is correct
8 Correct 131 ms 38232 KB Output is correct
9 Correct 144 ms 38648 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct
3 Correct 19 ms 23928 KB Output is correct
4 Correct 19 ms 23928 KB Output is correct
5 Incorrect 19 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -