Submission #1012830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012830		fryingduc	Triple Jump (JOI19_jumps)	C++17	0 / 100	42 ms	49744 KiB

jumps

#include "bits/stdc++.h"
using namespace std;

const int maxn = 5e5 + 5;

const int inf = 1e9;

int n, q, a[maxn];

struct node {
    long long res;
    int pos[3];
    node() {
        for(int i = 0; i < 3; ++i) pos[i] = 0;
        res = 0;
    }
    node(int r, int x, int y, int z) { 
        res = r;
        pos[0] = x, pos[1] = y, pos[2] = z;
    }
    node operator+(const node &o) const {
        vector<int> cur;
        node tmp;
        for(int i = 0; i < 3; ++i) {
            if(pos[i]) cur.push_back(pos[i]);
        }
        for(int i  = 0; i < 3; ++i) {
            if(o.pos[i]) cur.push_back(o.pos[i]);
        }
        if(cur.size() < 3) {
            for(int i = 0; i < (int)cur.size(); ++i) {
                tmp.pos[i] = cur[i];
                tmp.res += a[cur[i]];                
            }
            return tmp;
        }
        for(int i = 2; i < (int)cur.size(); ++i) {
            for(int j = 1; j < i; ++j) {
                for(int k = 0; k < j; ++k) {
                    if(cur[j] - cur[k] <= cur[i] - cur[j]) {
                        if(tmp.res < a[cur[i]] + a[cur[j]] + a[cur[k]]) {
                            tmp.res = a[cur[i]] + a[cur[j]] + a[cur[k]];
                            tmp.pos[0] = cur[k], tmp.pos[1] = cur[j], tmp.pos[2] = cur[i];
                        }
                    }
                }
            }
        }
        return tmp;
    }
} tree[maxn * 4];
struct segment_tree {
    int n;
    segment_tree() {}
    segment_tree(int n) : n(n) {}
    void build(int ind, int l, int r) {
        if(l == r) {
            tree[ind] = {a[l], l, 0, 0};
            return;
        }
        int mid = (l + r) / 2;
        build(ind * 2, l, mid);
        build(ind * 2 + 1, mid + 1, r);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    node get(int ind, int l, int r, int x, int y) {
        if(l > y || r < x) return node();
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
    }
    node get(int x, int y) {
        return get(1, 1, n, x, y);
    }
} st;
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    st = segment_tree(n);
    st.build(1, 1, n);
    cin >> q;
    while(q--) {
        int l, r; cin >> l >> r;
        cout << st.get(l, r).res << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54