Submission #807390

#	Time	Username	Problem	Language	Result	Execution time	Memory
807390		someone	Triple Jump (JOI19_jumps)	C++14	5 / 100	4059 ms	45028 KiB

jumps

#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 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54