oj.uz

Submission #349051

# Submission time Handle Problem Language Result Execution time Memory
349051 2021-01-16T12:30:13 Z Vanjanja Triple Jump (JOI19_jumps) C++14
46 / 100
 2052 ms 59824 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500001;
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 && c[ind].second) {
        int l = 2 * c[ind].second - i;
        if (l < n) {
            update(0, 0, n - 1, l, n - 1, a[i] + 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);
    }
    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 9 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 10 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 10 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 9 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 10 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 10 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 1425 ms 26336 KB Output is correct
12 Correct 1385 ms 31084 KB Output is correct
13 Correct 1383 ms 31084 KB Output is correct
14 Correct 1431 ms 31168 KB Output is correct
15 Correct 1517 ms 31188 KB Output is correct
16 Correct 1367 ms 30404 KB Output is correct
17 Correct 1361 ms 30432 KB Output is correct
18 Correct 1393 ms 30372 KB Output is correct
19 Correct 1369 ms 30952 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 21464 KB Output is correct
2 Correct 94 ms 20036 KB Output is correct
3 Correct 95 ms 21188 KB Output is correct
4 Correct 161 ms 21484 KB Output is correct
5 Correct 163 ms 21484 KB Output is correct
6 Correct 157 ms 21356 KB Output is correct
7 Correct 160 ms 21356 KB Output is correct
8 Correct 159 ms 21484 KB Output is correct
9 Correct 155 ms 21484 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 10 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 10 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 1425 ms 26336 KB Output is correct
12 Correct 1385 ms 31084 KB Output is correct
13 Correct 1383 ms 31084 KB Output is correct
14 Correct 1431 ms 31168 KB Output is correct
15 Correct 1517 ms 31188 KB Output is correct
16 Correct 1367 ms 30404 KB Output is correct
17 Correct 1361 ms 30432 KB Output is correct
18 Correct 1393 ms 30372 KB Output is correct
19 Correct 1369 ms 30952 KB Output is correct
20 Correct 157 ms 21464 KB Output is correct
21 Correct 94 ms 20036 KB Output is correct
22 Correct 95 ms 21188 KB Output is correct
23 Correct 161 ms 21484 KB Output is correct
24 Correct 163 ms 21484 KB Output is correct
25 Correct 157 ms 21356 KB Output is correct
26 Correct 160 ms 21356 KB Output is correct
27 Correct 159 ms 21484 KB Output is correct
28 Correct 155 ms 21484 KB Output is correct
29 Incorrect 2052 ms 59824 KB Output isn't correct
30 Halted 0 ms 0 KB -