oj.uz

Submission #674196

# Submission time Handle Problem Language Result Execution time Memory
674196 2022-12-23T12:21:09 Z MohamedFaresNebili Triple Jump (JOI19_jumps) C++14
100 / 100
 1008 ms 84260 KB 
#include <bits/stdc++.h>

		using namespace std;
		using ll = long long;

		#define int ll

		int N, Q, A[500005], res[500005];
		array<int, 3> ST[2000005];
		void build(int v, int l, int r) {
            if(l == r) {
                ST[v] = {A[l], 0, A[l]};
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            ST[v][0] = max(ST[v * 2][0], ST[v * 2 + 1][0]);
            ST[v][1] = max(ST[v * 2][1], ST[v * 2 + 1][1]);
            ST[v][2] = max({ST[v * 2][2], ST[v * 2 + 1][2], ST[v * 2][1] + ST[v * 2 + 1][0]});
		}
		void update(int v, int l, int r, int p, int val) {
            if(l == r) {
                ST[v][1] = max(ST[v][1], val);
                ST[v][2] = ST[v][0] + ST[v][1];
                return;
            }
            int md = (l + r) / 2;
            if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
            else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
            ST[v][0] = max(ST[v * 2][0], ST[v * 2 + 1][0]);
            ST[v][1] = max(ST[v * 2][1], ST[v * 2 + 1][1]);
            ST[v][2] = max({ST[v * 2][2], ST[v * 2 + 1][2], ST[v * 2][1] + ST[v * 2 + 1][0]});
		}
		array<int, 3> query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return {-1, -1, -1};
            if(l >= lo && r <= hi) return ST[v];
            array<int, 3> U = query(v * 2, l, (l + r) / 2, lo, hi);
            array<int, 3> V = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
            if(U[0] == -1) return V;
            if(V[0] == -1) return U;
            array<int, 3> ans;
            ans[0] = max(U[0], V[0]);
            ans[1] = max(U[1], V[1]);
            ans[2] = max({U[2], V[2], U[1] + V[0]});
            return ans;
		}
		bool compare(array<int, 3> U, array<int, 3> V) {
            if(U[0] != V[0]) return U[0] > V[0];
            return U[2] < V[2];
		}

		int32_t main() {
			ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
			cin >> N; stack<int> S;
			for(int l = 1; l <= N; l++)
                cin >> A[l];
            cin >> Q; build(1, 1, N);
            vector<array<int, 3>> E;
            for(int l = 1; l <= N; l++) {
                while(!S.empty() && A[S.top()] <= A[l]) {
                    E.push_back({S.top(), l, -1});
                    S.pop();
                }
                if(!S.empty()) E.push_back({S.top(), l, -1});
                S.push(l);
            }
            for(int l = 1; l <= Q; l++) {
                int L, R; cin >> L >> R;
                E.push_back({L, R, l});
            }
            sort(E.begin(), E.end(), compare);
            for(auto u : E) {
                if(u[2] == -1) {
                    int k = 2 * u[1] - u[0];
                    if(k > N) continue;
                    update(1, 1, N, k, A[u[0]] + A[u[1]]);
                } else {
                    res[u[2]] = query(1, 1, N, u[0], u[1])[2];
                }
            }
            for(int l = 1; l <= Q; l++)
                cout << res[l] << "\n";
		}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 356 ms 26484 KB Output is correct
12 Correct 327 ms 26240 KB Output is correct
13 Correct 316 ms 26364 KB Output is correct
14 Correct 313 ms 26408 KB Output is correct
15 Correct 350 ms 26404 KB Output is correct
16 Correct 348 ms 25884 KB Output is correct
17 Correct 323 ms 25692 KB Output is correct
18 Correct 330 ms 25708 KB Output is correct
19 Correct 356 ms 26400 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 28364 KB Output is correct
2 Correct 120 ms 22208 KB Output is correct
3 Correct 113 ms 23128 KB Output is correct
4 Correct 147 ms 28348 KB Output is correct
5 Correct 145 ms 28344 KB Output is correct
6 Correct 143 ms 27836 KB Output is correct
7 Correct 135 ms 27528 KB Output is correct
8 Correct 178 ms 27644 KB Output is correct
9 Correct 140 ms 27968 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 356 ms 26484 KB Output is correct
12 Correct 327 ms 26240 KB Output is correct
13 Correct 316 ms 26364 KB Output is correct
14 Correct 313 ms 26408 KB Output is correct
15 Correct 350 ms 26404 KB Output is correct
16 Correct 348 ms 25884 KB Output is correct
17 Correct 323 ms 25692 KB Output is correct
18 Correct 330 ms 25708 KB Output is correct
19 Correct 356 ms 26400 KB Output is correct
20 Correct 138 ms 28364 KB Output is correct
21 Correct 120 ms 22208 KB Output is correct
22 Correct 113 ms 23128 KB Output is correct
23 Correct 147 ms 28348 KB Output is correct
24 Correct 145 ms 28344 KB Output is correct
25 Correct 143 ms 27836 KB Output is correct
26 Correct 135 ms 27528 KB Output is correct
27 Correct 178 ms 27644 KB Output is correct
28 Correct 140 ms 27968 KB Output is correct
29 Correct 921 ms 84080 KB Output is correct
30 Correct 730 ms 72264 KB Output is correct
31 Correct 731 ms 76208 KB Output is correct
32 Correct 912 ms 84140 KB Output is correct
33 Correct 920 ms 84260 KB Output is correct
34 Correct 907 ms 81848 KB Output is correct
35 Correct 910 ms 81540 KB Output is correct
36 Correct 1008 ms 81492 KB Output is correct
37 Correct 935 ms 83024 KB Output is correct
38 Correct 721 ms 84084 KB Output is correct
39 Correct 710 ms 84000 KB Output is correct
40 Correct 685 ms 81656 KB Output is correct
41 Correct 701 ms 81404 KB Output is correct
42 Correct 697 ms 81432 KB Output is correct
43 Correct 693 ms 82256 KB Output is correct
44 Correct 727 ms 84084 KB Output is correct
45 Correct 781 ms 84040 KB Output is correct
46 Correct 754 ms 81632 KB Output is correct
47 Correct 726 ms 81360 KB Output is correct
48 Correct 723 ms 81372 KB Output is correct
49 Correct 689 ms 82720 KB Output is correct
50 Correct 755 ms 84144 KB Output is correct
51 Correct 759 ms 84216 KB Output is correct
52 Correct 731 ms 81920 KB Output is correct
53 Correct 770 ms 81556 KB Output is correct
54 Correct 745 ms 81456 KB Output is correct
55 Correct 756 ms 83048 KB Output is correct