Submission #145583

#	Time	Username	Problem	Language	Result	Execution time	Memory
145583		2fat2code	Triple Jump (JOI19_jumps)	C++14	100 / 100	1178 ms	88544 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
///#define cin fin
///#define cout fout
using namespace std;


//ofstream fout("file.out");

const int nmax=1e3+5;
const int mod=1e9+7;
const int mod1=998244353;



int n,a[500005],q,l,r,curr,pop,lazy[2000005];
vector<pair<int,int>>par;
vector<pair<pair<int,int>,int>>que;
vector<pair<int,int>>ans;
pair<int,int>tree[2000005];
stack<int>st;

void createsegtree(int l,int r,int indx){
    if(l==r) tree[indx].sc = a[l];
    else{
        int mid = l+(r-l)/2;
        createsegtree(l,mid,2*indx);
        createsegtree(mid+1,r,2*indx+1);
        tree[indx].sc = max(tree[2*indx].sc,tree[2*indx+1].sc);
    }
}

void update(int rangeleft,int rangeright,int val,int lef,int rig,int indx){
    if(lazy[indx]!=0){
        tree[indx].fr=max(tree[indx].fr,lazy[indx]+tree[indx].sc);
        if(lef!=rig){
            lazy[2*indx]=max(lazy[2*indx],lazy[indx]);
            lazy[2*indx+1]=max(lazy[2*indx+1],lazy[indx]);
        }
        lazy[indx]=0;
    }
    if(lef>rangeright || rig<rangeleft) return;
    else if(rangeleft<=lef && rangeright>=rig){
        tree[indx].fr=max(tree[indx].fr,val+tree[indx].sc);
        if(lef!=rig){
            lazy[2*indx]=max(lazy[2*indx],val);
            lazy[2*indx+1]=max(lazy[2*indx+1],val);
        }
    }
    else{
        int mid=lef+(rig-lef)/2;
        update(rangeleft,rangeright,val,lef,mid,2*indx);
        update(rangeleft,rangeright,val,mid+1,rig,2*indx+1);
        tree[indx].fr=max(tree[2*indx].fr,tree[2*indx+1].fr);
    }
}

int check(int rangeleft,int rangeright,int lef,int rig,int indx){
    if(lazy[indx]!=0){
        tree[indx].fr=max(tree[indx].fr,lazy[indx]+tree[indx].sc);
        if(lef!=rig){
            lazy[2*indx]=max(lazy[2*indx],lazy[indx]);
            lazy[2*indx+1]=max(lazy[2*indx+1],lazy[indx]);
        }
        lazy[indx]=0;
    }
    if(rangeright<lef || rangeleft>rig) return 0;
    else if(rangeleft<=lef && rangeright>=rig){
        return tree[indx].fr;
    }
    else{
        int mid=lef+(rig-lef)/2;
        return max(check(rangeleft,rangeright,lef,mid,2*indx),check(rangeleft,rangeright,mid+1,rig,2*indx+1));
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	cin >> q;
	for(int i=1;i<=q;i++){
        cin >> l >> r;
        que.push_back({{l,r},i});
	}
	sort(all(que));
	for(int i=1;i<n;i++){
        while(!st.empty() && a[st.top()]<=a[i]){
            par.push_back({st.top(),i});
            st.pop();
        }
        if(!st.empty()){
            par.push_back({st.top(),i});
        }
        st.push(i);
	}
    createsegtree(1,n,1);
    sort(all(par));
    curr=par.size()-1,pop=que.size()-1;
    for(int i=n-2;i>=1;i--){
        while(curr>=0 && par[curr].fr==i){
            update(2*par[curr].sc-par[curr].fr,n,a[par[curr].fr]+a[par[curr].sc],1,n,1);
            curr--;
        }
        while(pop>=0 && que[pop].fr.fr==i){
            ans.push_back({que[pop].sc,check(que[pop].fr.fr,que[pop].fr.sc,1,n,1)});
            pop--;
        }
    }
    sort(all(ans));
    for(int i=0;i<ans.size();i++){
        cout << ans[i].sc << '\n';
    }
}

Compilation message (stderr)

jumps.cpp: In function 'int32_t main()':
jumps.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++){
                 ~^~~~~~~~~~~

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