oj.uz

Submission #807390

# Submission time Handle Problem Language Result Execution time Memory
807390 2023-08-04T16:40:00 Z someone Triple Jump (JOI19_jumps) C++14
5 / 100
 4000 ms 45028 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 = -INF, maxABC = -INF, 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--;
        int maxi = 0;
        for(int A = deb[i]; A <= fin; A++)
            for(int b = A+1; b <= fin; b++)
                for(int c = b+1; c <= fin; c++)
                    if(b - A <= c - b)
                        maxi = max(maxi, a[A] + a[b] + a[c]);
        cout << maxi << '\n';
        //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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37204 KB Output is correct
2 Correct 17 ms 37204 KB Output is correct
3 Correct 18 ms 37264 KB Output is correct
4 Correct 17 ms 37292 KB Output is correct
5 Correct 19 ms 37428 KB Output is correct
6 Correct 16 ms 37204 KB Output is correct
7 Correct 17 ms 37268 KB Output is correct
8 Correct 18 ms 37232 KB Output is correct
9 Correct 18 ms 37204 KB Output is correct
10 Correct 18 ms 37268 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37204 KB Output is correct
2 Correct 17 ms 37204 KB Output is correct
3 Correct 18 ms 37264 KB Output is correct
4 Correct 17 ms 37292 KB Output is correct
5 Correct 19 ms 37428 KB Output is correct
6 Correct 16 ms 37204 KB Output is correct
7 Correct 17 ms 37268 KB Output is correct
8 Correct 18 ms 37232 KB Output is correct
9 Correct 18 ms 37204 KB Output is correct
10 Correct 18 ms 37268 KB Output is correct
11 Execution timed out 4051 ms 37444 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 45028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 37204 KB Output is correct
2 Correct 17 ms 37204 KB Output is correct
3 Correct 18 ms 37264 KB Output is correct
4 Correct 17 ms 37292 KB Output is correct
5 Correct 19 ms 37428 KB Output is correct
6 Correct 16 ms 37204 KB Output is correct
7 Correct 17 ms 37268 KB Output is correct
8 Correct 18 ms 37232 KB Output is correct
9 Correct 18 ms 37204 KB Output is correct
10 Correct 18 ms 37268 KB Output is correct
11 Execution timed out 4051 ms 37444 KB Time limit exceeded
12 Halted 0 ms 0 KB -