Submission #957725

#	Time	Username	Problem	Language	Result	Execution time	Memory
957725		parlimoos	Triple Jump (JOI19_jumps)	C++14	100 / 100	863 ms	102600 KiB

jumps

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , q , o[500000];
vector<int> a , ps[500000];
vector<arr(2)> ops[500000];
int seg[2000001][2] , seginf[2000001][2] , laz[2000001];

void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r , laz[i] = 0;
    if(l == r) seg[i][0] = a[l];
    else{
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
        seg[i][0] = max(seg[i << 1][0] , seg[(i << 1) | 1][0]);
    }
    seg[i][1] = seg[i][0];
}
void pushSeg(int i){
    for(int ch = (i << 1) ; ch <= ((i << 1) | 1) ; ch++){
        seg[ch][1] = max(seg[ch][1] , seg[ch][0] + laz[i]);
        laz[ch] = max(laz[ch] , laz[i]);
    }
    laz[i] = 0;
}
void addSeg(int l , int r , int i , int val){
    if(seginf[i][0] >= l and seginf[i][1] <= r){
        seg[i][1] = max(seg[i][1] , seg[i][0] + val);
        laz[i] = max(laz[i] , val);
    }else if(seginf[i][1] >= l and seginf[i][0] <= r){
        pushSeg(i);
        addSeg(l , r , i << 1 , val) , addSeg(l , r , (i << 1) | 1 , val);
        seg[i][1] = max(seg[i << 1][1] , seg[(i << 1) | 1][1]);
    }
}
int getSeg(int l , int r , int i){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i][1];
    if(seginf[i][1] >= l and seginf[i][0] <= r){
        pushSeg(i);
        return max(getSeg(l , r , i << 1) , getSeg(l , r , (i << 1) | 1));
    }
    return 0;
}
void init(){
    stack<int> hds;
    for(int i = 0 ; i < n ; i++){
        while(!hds.empty() and a[hds.top()] <= a[i]){
            ps[hds.top()].pb(i);
            hds.pop();
        }
        if(!hds.empty()) ps[hds.top()].pb(i);
        hds.push(i);
    }
}
void f(){
    for(int l = n - 1 ; l >= 0 ; l--){
        for(int r : ps[l]){
            int inx = r + r - l;
            if(inx <= n - 1) addSeg(inx , n - 1 , 1 , a[l] + a[r]);
        }
        for(auto &op : ops[l]){
            o[op[1]] = getSeg(l , op[0] , 1);
        }
    }
}

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

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int d;
        cin >> d;
        a.pb(d);
    }
    cin >> q;
    for(int i = 0 ; i < q ; i++){
        int l , r;
        cin >> l >> r;
        l-- , r--;
        ops[l].pb({r , i});
    }
    buildSeg() , init() , f();
    for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}

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