Submission #677747

#	Time	Username	Problem	Language	Result	Execution time	Memory
677747		Cross_Ratio	Triple Jump (JOI19_jumps)	C++14	27 / 100	214 ms	14200 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
    int val, mi, ma;
    Node():val(0), mi(0), ma(0) {}
    Node(int _v, int _i, int _a) : val(_v), mi(_i), ma(_a) {}
};
struct SegTree {
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    Node f(Node x, Node y) {
        if(x.val>y.val) return x;
        if(x.val<y.val) return y;
        return Node(x.val, min(x.mi, y.mi), max(x.ma, y.ma));
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = f(seg[2*i], seg[2*i+1]);
        }
    }
    Node sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return Node();
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return f(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[500005];
int B[5005][5005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    SegTree tree(N);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) tree.seg[i+MAX/2] = Node(A[i],i,i);
    tree.cons();
    /*for(int l = 0; l < N; l++) {
        for(int r = l + 2; r < N; r++) {
            B[l][r] = A[l]+A[r]+tree.sum(l+1, (l+r)/2+1, 1, 0, MAX/2);
        }
    }*/
    /*for(int len = 3; len <= N-1; len++) {
        for(i=0;i+len<=N-1;i++) {
            B[i][i+len] = max(B[i][i+len], B[i+1][i+len]);
            B[i][i+len] = max(B[i][i+len], B[i][i+len-1]);
        }
    }*/
    int Q;
    cin >> Q;
    while(Q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        int ans = 0;
        for(i=l;i<=r-2;i++) {
            Node v = tree.sum(i+2, r+1, 1, 0, MAX/2);
            int id = v.ma;
            v = tree.sum(i+1, (i+id)/2+1, 1, 0, MAX/2);
            ans = max(ans, A[i] + A[id] + v.val);
            v = tree.sum(i+1, (i+r)/2+1, 1, 0, MAX/2);
            id = v.mi;
            v = tree.sum(2*id - i, r+1, 1, 0, MAX/2);
            ans = max(ans, A[i] + A[id] + v.val);
        }
        cout << ans << '\n';
    }

}

Compilation message (stderr)

jumps.cpp: In member function 'Node SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
   43 |     int i, j;
      |            ^

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