Submission #409242

#	Time	Username	Problem	Language	Result	Execution time	Memory
409242		cpp219	Triple Jump (JOI19_jumps)	C++14	100 / 100	1876 ms	115616 KiB

jumps

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 5e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;

struct Query{
    ll R,id;
};
vector<Query> q[N];
vector<ll> cand[N];
ll n,a[N],Q,L,R,lazy[4*N],ans[N];
stack<ll> S;

struct Node{
    ll inc,val,ans;
};
Node st[4*N];

Node operator + (Node a,Node b){
    Node res;
    res.ans = max(a.ans,max(b.ans,a.inc + b.val));
    res.inc = max(a.inc,b.inc);
    res.val = max(a.val,b.val);
    return res;
}

void Pass(ll id){
    ll t = lazy[id];
    lazy[id*2] = max(lazy[id*2],t); lazy[id*2 + 1] = max(lazy[id*2 + 1],t);
    st[id*2].inc = max(st[id*2].inc,t); st[id*2 + 1].inc = max(st[id*2 + 1].inc,t);
    st[id*2].ans = max(st[id*2].ans,t + st[id*2].val);
    st[id*2 + 1].ans = max(st[id*2 + 1].ans,t + st[id*2 + 1].val);
}

void upd_inc(ll id,ll l,ll r,ll u,ll v,ll gt){
    if (v < l||r < u) return;
    //if (u == 4&&v == 6&&gt == 22) cout<<lazy[id]<<"x\n";
    if (u <= l&&r <= v){
        st[id].inc = max(st[id].inc,gt); lazy[id] = max(lazy[id],gt);
        st[id].ans = max(st[id].ans,gt + st[id].val);
        return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd_inc(id*2,l,mid,u,v,gt); upd_inc(id*2 + 1,mid + 1,r,u,v,gt);
    st[id] = st[id*2] + st[id*2 + 1];
}

void upd_val(ll id,ll l,ll r,ll u,ll gt){
    if (u < l||r < u) return;
    if (l == r){
        st[id].val = gt; return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd_val(id*2,l,mid,u,gt); upd_val(id*2 + 1,mid + 1,r,u,gt);
    st[id] = st[id*2] + st[id*2 + 1];
}

Node Get(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return {0,0,0};
    //if (u == 2&&v == 5) cout<<id<<" "<<l<<" "<<r<<"\n";
    if (u <= l&&r <= v) return st[id];
    ll mid = (l + r)/2; Pass(id);

    return Get(id*2,l,mid,u,v) + Get(id*2 + 1,mid + 1,r,u,v);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i];
    for (ll i = 1;i <= n;i++){
        while(!S.empty() && a[S.top()] <= a[i]) cand[S.top()].push_back(i),S.pop();
        if (!S.empty()) cand[S.top()].push_back(i);
        S.push(i);
    }
    //for (auto i : cand[2]) cout<<i<<" ";
    //cout<<Get(1,1,n,1,n).ans;
    //return 0;
    cin>>Q;
    for (ll i = 1;i <= Q;i++) cin>>L>>R,q[L].push_back({R,i});
    for (ll i = n;i > 0;i--){
        upd_val(1,1,n,i,a[i]);
        for (auto j : cand[i]){
            upd_inc(1,1,n,2*j - i,n,a[i] + a[j]);
        }
        for (auto j : q[i]) ans[j.id] = Get(1,1,n,i,j.R).ans;
    }
    for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

jumps.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
jumps.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
jumps.cpp: In function 'int main()':
jumps.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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