Submission #1158390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158390		trantrungkein	Triple Jump (JOI19_jumps)	C++20	0 / 100	103 ms	5168 KiB

jumps

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 7;
struct node
{
    int f,m,s,sum;
} st[4*N];
int maxx = 0,f[N],n,q;
void check(int a, int b, int c, node& tmp)
{   if(a == 0 || b == 0 || c == 0) return;
    if(b - a < c - b) return;
    int sum = f[a] + f[b] + f[c];
    if(sum > maxx) tmp = {a,b,c,sum};
}
node Merge(node a, node b)
{

    maxx = 0;
    node tmp;
    if(a.sum > maxx) tmp = a;
    if(b.sum > maxx) tmp = b;
    check(a.f,a.m,b.f, tmp);
    check(a.f,a.m,b.m, tmp);
    check(a.f,a.m,b.s, tmp);

    check(a.m,a.s,b.f, tmp);
    check(a.m,a.s,b.m, tmp);
    check(a.m,a.s,b.s, tmp);

    check(a.f,b.f,b.m, tmp);
    check(a.f,b.f,b.s, tmp);

    check(a.f,b.m,b.s, tmp);


    check(a.m,b.f,b.m, tmp);
    check(a.m,b.f,b.s, tmp);

    check(a.m,a.s,b.f, tmp);
    check(a.m,a.s,b.m, tmp);
    check(a.m,a.s,b.s, tmp);

    check(a.m,b.m,b.s, tmp);

    check(a.s,b.m,b.s, tmp);
    check(a.s,b.f,b.s, tmp);
    check(a.s,b.f,b.m, tmp);

    return tmp;
}
void update(int id, int l, int r, int p, int val)
{
    if(l > p || r < p) return;
    if(l == r)
    {
        st[id].f = 0;
        st[id].m = p;
        st[id].s = 0;
        st[id].sum = val;
        return;
    }
    int mid = (l+r)/2;
    update(2*id,l,mid,p,val);
    update(2*id+1,mid+1,r,p,val);
    st[id] = Merge(st[2*id],st[2*id+1]);
}
node get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u) return {0,0,0,-1};
    if(u <= l && r <= v) return st[id];
    int mid = (l+r)/2;
    return Merge(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> f[i], update(1,1,n,i,f[i]);
    cin >> q;
    while(q--)
    {
        int l,r;
        cin >> l >> r;
        cout << get(1,1,n,l,r).sum <<'\n';
    }
    return 0;
}

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