Submission #288387

#	Time	Username	Problem	Language	Result	Execution time	Memory
288387		alexandra_udristoiu	Triple Jump (JOI19_jumps)	C++14	100 / 100	1891 ms	46444 KiB

jumps

#include<iostream>
#include<algorithm>
#define DIM 500005
#define f first
#define s second
using namespace std;
int n, q, i, u, nr;
int v[DIM], c[DIM], sol[DIM];
pair<int, int> p[2 * DIM];
struct str{
    int x, y, ind;
};
str w[DIM];
struct str2{
    int vmax, smax, cmax;
};
str2 aint[4 * DIM], curr;
int cmp(str a, str b){
    return a.x > b.x;
}
void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].vmax = v[st];
    }
    else{
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        aint[nod].vmax = max(aint[2 * nod].vmax, aint[2 * nod + 1].vmax);
    }
}
void update(int nod, int st, int dr, int p, int u, int val){
    if(p <= st && dr <= u){
        aint[nod].cmax = max(aint[nod].cmax, val);
        aint[nod].smax = max(aint[nod].smax, aint[nod].vmax + aint[nod].cmax);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, u, val);
        }
        if(u > mid){
            update(2 * nod + 1, mid + 1, dr, p, u, val);
        }
        aint[nod].smax = max(aint[nod].smax, max(aint[2 * nod].smax, aint[2 * nod + 1].smax) );
    }
}
str2 query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        return aint[nod];
    }
    else{
        int mid = (st + dr) / 2;
        str2 a, b, curr;
        a = b = {0, 0, 0};
        if(p <= mid){
            a = query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            b = query(2 * nod + 1, mid + 1, dr, p, u);
        }
        curr.vmax = max(a.vmax, b.vmax);
        curr.cmax = aint[nod].cmax;
        curr.smax = max(curr.vmax + curr.cmax, max(a.smax, b.smax) );
        return curr;
    }
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> v[i];
    }
    for(i = n; i >= 1; i--){
        while(u > 0 && v[ c[u] ] < v[i]){
            p[++nr] = make_pair(i, c[u]);
            u--;
        }
        if(u > 0){
            p[++nr] = make_pair(i, c[u]);
        }
        c[++u] = i;
    }
    sort(p + 1, p + nr + 1);
    build(1, 1, n);
    cin>> q;
    for(i = 1; i <= q; i++){
        cin>> w[i].x >> w[i].y;
        w[i].ind = i;
    }
    sort(w + 1, w + q + 1, cmp);
    u = nr;
    for(i = 1; i <= q; i++){
        while(u > 0 && p[u].f >= w[i].x){
            if(p[u].s + p[u].s - p[u].f <= n){
                update(1, 1, n, p[u].s + p[u].s - p[u].f, n, v[ p[u].f ] + v[ p[u].s ]);
            }
            u--;
        }
        curr = query(1, 1, n, w[i].x, w[i].y);
        sol[ w[i].ind ] = curr.smax;
    }
    for(i = 1; i <= q; i++){
        cout<< sol[i] <<"\n";
    }
}

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