oj.uz

Submission #145577

# Submission time Handle Problem Language Result Execution time Memory
145577 2019-08-20T12:23:07 Z 2fat2code Triple Jump (JOI19_jumps) C++14
32 / 100
 373 ms 62668 KB 
#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[8000005];
vector<pair<int,int>>par;
vector<pair<pair<int,int>,int>>que;
vector<pair<int,int>>ans;
pair<int,int>tree[8000005];
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(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(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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Runtime error 373 ms 62668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 22356 KB Output is correct
2 Correct 103 ms 19220 KB Output is correct
3 Correct 105 ms 20664 KB Output is correct
4 Correct 192 ms 22356 KB Output is correct
5 Correct 196 ms 22484 KB Output is correct
6 Correct 178 ms 21664 KB Output is correct
7 Correct 178 ms 21716 KB Output is correct
8 Correct 177 ms 21564 KB Output is correct
9 Correct 181 ms 22044 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Runtime error 373 ms 62668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -