oj.uz

Submission #349075

# Submission time Handle Problem Language Result Execution time Memory
349075 2021-01-16T14:41:14 Z Vanjanja Triple Jump (JOI19_jumps) C++14
46 / 100
 2075 ms 49708 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
int a[N];
vector<pair<int, int>> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[2 * N - 1][2];
int lazy[2 * N - 1];
int n;
int ind = 0;

void build(int u, int l, int r) {
    if (l == r) {
        seg[u][1] = a[l];
        return;
    }
    int mid  = (l + r) >> 1;
    build(u * 2 + 1, l, mid);
    build(u * 2 + 2, mid + 1, r);
    seg[u][1] = max(seg[u * 2 + 1][1], seg[u * 2 + 2][1]);
}

void upd(int u, int x) {
    seg[u][0] = max(seg[u][0], x + seg[u][1]);
    lazy[u] = max(lazy[u], x);
}

void shift(int u) {
    if (!lazy[u])
        return;
    upd(u * 2 + 1, lazy[u]);
    upd(u * 2 + 2, lazy[u]);
    lazy[u] = 0;
}

void update(int u, int l, int r, int L, int R, int x) {
    if (r < L || l > R)
        return;
    if (l >= L && r <= R) {
        upd(u, x);
        return;
    }
    shift(u);
    int mid = (l + r) >> 1;
    update(u * 2 + 1, l, mid, L, R, x);
    update(u * 2 + 2, mid + 1, r, L, R, x);
    seg[u][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 2][0]);
}

void Update(int i) {
    if (b[i]) {
        int l = 2 * b[i] - i;
        if (l < n) {
            update(0, 0, n - 1, l, n - 1, a[i] + a[b[i]]);
        }
    }
    while (c[ind].first == i) {
        int l = 2 * c[ind].second - c[ind].first;
        if (l < n) {
            update(0, 0, n - 1, l, n - 1, a[c[ind].first] + a[c[ind].second]);
        }
        ind++;
    }
}

int out(int u, int l, int r, int L, int R) {
    if (r < L || l > R)
        return 0;
    if (l >= L && r <= R) {
        return seg[u][0];
    }
    shift(u);
    int mid = (l + r) >> 1;
    return max(out(u * 2 + 1, l, mid, L, R), out(u * 2 + 2, mid + 1, r, L, R));
}

void veca(int n) {
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            b[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}

void veca1(int n) {
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            c[ind].first = i;
            c[ind++].second = s.top();
            s.pop();
        }
        s.push(i);
    }
    c[ind].first = -1;
    ind = 0;
}

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.first.first >= b.first.first;
}

void solve() {
    int q;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        que[l - 1].push_back({r - 1, i});
    }
    veca(n);
    veca1(n);
    build(0, 0, n - 1);
    for (int i = n - 1; i >= 0; i--) {
        Update(i);
        for (auto j = que[i].begin(); j != que[i].end(); j++) {
            pair<int, int> par = *j;
            resenje[par.second] = out(0, 0, n - 1, i, par.first);
        }
    }
    for (int i = 0; i < q; i++)
        cout << resenje[i] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 9 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 1361 ms 27000 KB Output is correct
12 Correct 1361 ms 27500 KB Output is correct
13 Correct 1373 ms 27208 KB Output is correct
14 Correct 1366 ms 27680 KB Output is correct
15 Correct 1358 ms 27628 KB Output is correct
16 Correct 1356 ms 26988 KB Output is correct
17 Correct 1379 ms 26860 KB Output is correct
18 Correct 1362 ms 26860 KB Output is correct
19 Correct 1372 ms 27436 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 21896 KB Output is correct
2 Correct 99 ms 20548 KB Output is correct
3 Correct 97 ms 21700 KB Output is correct
4 Correct 158 ms 21868 KB Output is correct
5 Correct 163 ms 21868 KB Output is correct
6 Correct 155 ms 21956 KB Output is correct
7 Correct 156 ms 22040 KB Output is correct
8 Correct 154 ms 21868 KB Output is correct
9 Correct 158 ms 21868 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 9 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 1361 ms 27000 KB Output is correct
12 Correct 1361 ms 27500 KB Output is correct
13 Correct 1373 ms 27208 KB Output is correct
14 Correct 1366 ms 27680 KB Output is correct
15 Correct 1358 ms 27628 KB Output is correct
16 Correct 1356 ms 26988 KB Output is correct
17 Correct 1379 ms 26860 KB Output is correct
18 Correct 1362 ms 26860 KB Output is correct
19 Correct 1372 ms 27436 KB Output is correct
20 Correct 161 ms 21896 KB Output is correct
21 Correct 99 ms 20548 KB Output is correct
22 Correct 97 ms 21700 KB Output is correct
23 Correct 158 ms 21868 KB Output is correct
24 Correct 163 ms 21868 KB Output is correct
25 Correct 155 ms 21956 KB Output is correct
26 Correct 156 ms 22040 KB Output is correct
27 Correct 154 ms 21868 KB Output is correct
28 Correct 158 ms 21868 KB Output is correct
29 Incorrect 2075 ms 49708 KB Output isn't correct
30 Halted 0 ms 0 KB -