Submission #515657

#	Time	Username	Problem	Language	Result	Execution time	Memory
515657		79brue	Triple Jump (JOI19_jumps)	C++14	100 / 100	836 ms	80104 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Query {
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};

struct segTree{
    struct Node{
        int l, r, v;
        Node(){}
        Node(int l, int r, int v): l(l), r(r), v(v){}

        Node operator+(const Node &nxt)const{
            return Node(max(l, nxt.l), max(r, nxt.r), max({v, nxt.v, l+nxt.r}));
        }
    } tree[2000002];

    void init(int i, int l, int r, int *arr){
        if(l==r){
            tree[i] = Node(-1e9, arr[l], -1e9);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Node query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return Node(-1e9, -1e9, -1e9);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i].l = max(tree[i].l, v);
            tree[i].v = max(tree[i].v, tree[i].l+tree[i].r);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = tree[i*2] + tree[i*2+1];
    }
} tree;

int n, q;
int arr[500002];
vector<int> interval[500002];
vector<Query> query[500002];
int ans[500002];

void makeInterval(){
    vector<pair<int, int> > vec;
    for(int i=1; i<=n; i++){
        while(!vec.empty() && vec.back().second <= arr[i]){
            interval[vec.back().first].push_back(i);
            vec.pop_back();
        }
        if(!vec.empty()) interval[vec.back().first].push_back(i);
        vec.push_back(make_pair(i, arr[i]));
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    makeInterval();
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        query[l].push_back(Query(l, r, i));
    }

    tree.init(1, 1, n, arr);
    for(int i=n-2; i>=1; i--){
        for(int j: interval[i]){
            if(2*j-i>n) continue;
            tree.update(1, 1, n, 2*j-i, arr[i]+arr[j]);
        }
        for(Query p: query[i]){
            ans[p.idx] = tree.query(1, 1, n, i, p.r).v;
        }
    }

    for(int i=1; i<=q; i++){
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:75:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
jumps.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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