제출 #163611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163611		combi1k1	3단 점프 (JOI19_jumps)	C++14	100 / 100	1741 ms	126968 KiB

jumps

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,a,b)  for(int i = a ; i <= b ; ++i)

#define X   first
#define Y   second

#define pb  push_back
#define ll  long long

#define lch     i << 1
#define rch     i << 1 | 1

#define Unit    Node(-2e9,-2e9,-3e9)

const int   N   = 5e5 + 1;

typedef pair<int,int>   ii;

struct Node {
    ll  L, R, S;

    Node(ll l = 0,ll r = 0,ll s = 0) : L(l), R(r), S(s) {}
}   tr[N << 2];

Node Spare;

Node operator + (const Node &a,const Node &b)   {
    ll x = max(a.L,b.L);
    ll y = max(a.R,b.R);
    ll z = max(a.S,b.S);

    return  Node(x,y,max(z,a.L + b.R));
}

void upd(int i,int l,int r,int p,int v,int t)   {
    if (l > p)  return;
    if (r < p)  return;
    if (l == r) {
        if (t)  tr[i].R = max(tr[i].R,(ll)v);
        else    tr[i].L = max(tr[i].L,(ll)v);

        tr[i].S = tr[i].L + tr[i].R;

        return;
    }
    int m = (l + r) / 2;

    upd(lch,l,m,p,v,t); ++m;
    upd(rch,m,r,p,v,t);

    tr[i] = tr[lch] + tr[rch];
}
void get(int i,int l,int r,int L,int R) {
    if (l > R)  return;
    if (L > r)  return;
    if (L <= l && r <= R)   {
        Spare = Spare + tr[i];
        return;
    }

    int m = (l + r) / 2;

    get(lch,l,m,L,R);   ++m;
    get(rch,m,r,L,R);
}

vector<ii>  Que[N];
vector<ii>  Seg[N];

int a[N];
int t[N];
int tot = 0;

ll  ans[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    fill(tr + 1,tr + 4 * n,Unit);

    auto add = [&](int x,int y) {
        if (y + y <= n + x)
            Seg[x].pb(ii(y + y - x,a[x] + a[y]));
    };
    auto ask = [&](int l,int r) {
        Spare = Unit;
        get(1,1,n,l,r);

        return  Spare.S;
    };

    FOR(i,1,n)  {
        cin >> a[i];
        for(; tot && a[t[tot]] < a[i] ; --tot)
            add(t[tot],i);
        if (tot)
            add(t[tot],i);

        t[++tot] = i;
    }

    int q;  cin >> q;

    FOR(i,1,q)  {
        int l;  cin >> l;
        int r;  cin >> r;

        Que[l].push_back(ii(r,i));
    }

    for(int i = n ; i >= 1 ; --i)   {
        upd(1,1,n,i,a[i],1);

        for(ii  e : Seg[i])
            upd(1,1,n,e.X,e.Y,0);
        for(ii  e : Que[i])
            ans[e.Y] = ask(i,e.X);
    }

    FOR(i,1,q)  cout << ans[i] << "\n";
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

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