oj.uz

Submission #807381

# Submission time Handle Problem Language Result Execution time Memory
807381 2023-08-04T16:34:29 Z someone Triple Jump (JOI19_jumps) C++14
0 / 100
 189 ms 59176 KB 
#include <bits/stdc++.h>
//#define int long long
using namespace std;

const int M = 1 << 19, N = 2 * M, INF = 1e9 + 42;

struct Node {
    int maxAB, maxABC, tagC = -INF;
};

Node node[N];

void applyOp(int i, int newC) {
    node[i].tagC = max(node[i].tagC, newC);
    node[i].maxABC = max(node[i].maxABC, node[i].maxAB + newC);
}

void propage(int i) {
    applyOp(i*2, node[i].tagC);
    applyOp(i*2+1, node[i].tagC);
    node[i].tagC = -INF;
}

void insertAB(int i, int deb, int fin, int pos, int ab) {
    if(pos+1 <= deb || fin <= pos) return;
    if(fin - deb == 1) {
        node[i].maxAB = max(node[i].maxAB, ab);
        return;
    }
    propage(i);
    int mid = ((deb + fin) >> 1);
    insertAB(i*2, deb, mid, pos, ab);
    insertAB(i*2+1, mid, fin, pos, ab);
    node[i].maxAB = max(node[i*2].maxAB, node[i*2+1].maxAB);
}

int update(int i, int deb, int fin, int l, int r, int newC) {
    if(fin <= l || r <= deb) return -INF;
    if(l <= deb && fin <= r) {
        applyOp(i, newC);
        return node[i].maxABC;
    }
    propage(i);
    int mid = ((deb + fin) >> 1),
        ans = max(update(i*2, deb, mid, l, r, newC),
                  update(i*2+1, mid, fin, l, r, newC));
    node[i].maxABC = max(node[i*2].maxABC, node[i*2+1].maxABC);
    return ans;
}

vector<int> req[M];
vector<pair<int, int>> ab[N];
int n, q, a[N], deb[M], ans[M];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    deque<int> imax;
    for(int i = 0; i < n; i++) {
        while(!imax.empty() && a[imax[0]] < a[i]) {
            ab[2*i - imax[0]].push_back({imax[0], a[imax[0]] + a[i]});
            imax.pop_front();
        }
        imax.push_front(i);
    }
    imax.clear();
    for(int i = n-1; i > -1; i--) {
        while(!imax.empty() && a[imax[0]] < a[i]) {
            ab[2 * imax[0] - i].push_back({i, a[imax[0]] + a[i]});
            imax.pop_front();
        }
        imax.push_front(i);
    }

    cin >> q;
    for(int i = 0; i < q; i++) {
        int fin; cin >> deb[i] >> fin;
        deb[i]--, fin--;
        req[fin].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        for(auto pii : ab[i])
            insertAB(1, 0, M, pii.first, pii.second);
        update(1, 0, M, 0, i, a[i]);
        for(int id : req[i])
            ans[id] = update(1, 0, M, deb[id], i+1, -INF);
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49576 KB Output is correct
2 Correct 22 ms 49576 KB Output is correct
3 Correct 20 ms 49472 KB Output is correct
4 Correct 21 ms 49580 KB Output is correct
5 Correct 24 ms 49572 KB Output is correct
6 Incorrect 20 ms 49584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49576 KB Output is correct
2 Correct 22 ms 49576 KB Output is correct
3 Correct 20 ms 49472 KB Output is correct
4 Correct 21 ms 49580 KB Output is correct
5 Correct 24 ms 49572 KB Output is correct
6 Incorrect 20 ms 49584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 57772 KB Output is correct
2 Correct 134 ms 59176 KB Output is correct
3 Correct 142 ms 58368 KB Output is correct
4 Correct 189 ms 59128 KB Output is correct
5 Incorrect 181 ms 59052 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49576 KB Output is correct
2 Correct 22 ms 49576 KB Output is correct
3 Correct 20 ms 49472 KB Output is correct
4 Correct 21 ms 49580 KB Output is correct
5 Correct 24 ms 49572 KB Output is correct
6 Incorrect 20 ms 49584 KB Output isn't correct
7 Halted 0 ms 0 KB -