oj.uz

Submission #203859

# Submission time Handle Problem Language Result Execution time Memory
203859 2020-02-22T16:44:21 Z youngyojun Triple Jump (JOI19_jumps) C++11
100 / 100
 1127 ms 99704 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41464 KB Output is correct
2 Correct 30 ms 41464 KB Output is correct
3 Correct 31 ms 41464 KB Output is correct
4 Correct 30 ms 41464 KB Output is correct
5 Correct 32 ms 41464 KB Output is correct
6 Correct 30 ms 41464 KB Output is correct
7 Correct 34 ms 41480 KB Output is correct
8 Correct 30 ms 41464 KB Output is correct
9 Correct 37 ms 41464 KB Output is correct
10 Correct 32 ms 41464 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41464 KB Output is correct
2 Correct 30 ms 41464 KB Output is correct
3 Correct 31 ms 41464 KB Output is correct
4 Correct 30 ms 41464 KB Output is correct
5 Correct 32 ms 41464 KB Output is correct
6 Correct 30 ms 41464 KB Output is correct
7 Correct 34 ms 41480 KB Output is correct
8 Correct 30 ms 41464 KB Output is correct
9 Correct 37 ms 41464 KB Output is correct
10 Correct 32 ms 41464 KB Output is correct
11 Correct 376 ms 60408 KB Output is correct
12 Correct 378 ms 60408 KB Output is correct
13 Correct 389 ms 60408 KB Output is correct
14 Correct 379 ms 60280 KB Output is correct
15 Correct 383 ms 60408 KB Output is correct
16 Correct 380 ms 59768 KB Output is correct
17 Correct 392 ms 59640 KB Output is correct
18 Correct 391 ms 59768 KB Output is correct
19 Correct 374 ms 60280 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 51448 KB Output is correct
2 Correct 101 ms 50296 KB Output is correct
3 Correct 103 ms 51812 KB Output is correct
4 Correct 150 ms 51448 KB Output is correct
5 Correct 152 ms 51448 KB Output is correct
6 Correct 142 ms 50936 KB Output is correct
7 Correct 135 ms 50680 KB Output is correct
8 Correct 140 ms 50680 KB Output is correct
9 Correct 141 ms 51064 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41464 KB Output is correct
2 Correct 30 ms 41464 KB Output is correct
3 Correct 31 ms 41464 KB Output is correct
4 Correct 30 ms 41464 KB Output is correct
5 Correct 32 ms 41464 KB Output is correct
6 Correct 30 ms 41464 KB Output is correct
7 Correct 34 ms 41480 KB Output is correct
8 Correct 30 ms 41464 KB Output is correct
9 Correct 37 ms 41464 KB Output is correct
10 Correct 32 ms 41464 KB Output is correct
11 Correct 376 ms 60408 KB Output is correct
12 Correct 378 ms 60408 KB Output is correct
13 Correct 389 ms 60408 KB Output is correct
14 Correct 379 ms 60280 KB Output is correct
15 Correct 383 ms 60408 KB Output is correct
16 Correct 380 ms 59768 KB Output is correct
17 Correct 392 ms 59640 KB Output is correct
18 Correct 391 ms 59768 KB Output is correct
19 Correct 374 ms 60280 KB Output is correct
20 Correct 147 ms 51448 KB Output is correct
21 Correct 101 ms 50296 KB Output is correct
22 Correct 103 ms 51812 KB Output is correct
23 Correct 150 ms 51448 KB Output is correct
24 Correct 152 ms 51448 KB Output is correct
25 Correct 142 ms 50936 KB Output is correct
26 Correct 135 ms 50680 KB Output is correct
27 Correct 140 ms 50680 KB Output is correct
28 Correct 141 ms 51064 KB Output is correct
29 Correct 1120 ms 93120 KB Output is correct
30 Correct 1010 ms 90104 KB Output is correct
31 Correct 980 ms 89868 KB Output is correct
32 Correct 1127 ms 93100 KB Output is correct
33 Correct 1080 ms 93084 KB Output is correct
34 Correct 1081 ms 90820 KB Output is correct
35 Correct 1089 ms 90348 KB Output is correct
36 Correct 1113 ms 90432 KB Output is correct
37 Correct 1107 ms 91896 KB Output is correct
38 Correct 762 ms 99704 KB Output is correct
39 Correct 771 ms 99576 KB Output is correct
40 Correct 748 ms 96348 KB Output is correct
41 Correct 722 ms 95840 KB Output is correct
42 Correct 745 ms 95736 KB Output is correct
43 Correct 746 ms 97532 KB Output is correct
44 Correct 812 ms 99116 KB Output is correct
45 Correct 828 ms 99028 KB Output is correct
46 Correct 801 ms 95992 KB Output is correct
47 Correct 851 ms 95608 KB Output is correct
48 Correct 782 ms 95552 KB Output is correct
49 Correct 789 ms 97656 KB Output is correct
50 Correct 882 ms 96888 KB Output is correct
51 Correct 900 ms 96868 KB Output is correct
52 Correct 867 ms 94320 KB Output is correct
53 Correct 854 ms 94120 KB Output is correct
54 Correct 865 ms 94072 KB Output is correct
55 Correct 884 ms 95608 KB Output is correct