Submission #823471

#	Time	Username	Problem	Language	Result	Execution time	Memory
823471		Cookie	Triple Jump (JOI19_jumps)	C++14	100 / 100	1014 ms	105464 KiB

jumps

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxm = 1e5, sq = 400, mxv = 1e6 + 5;
const int base = (1 << 18);
const ll inf = 4e9, neg = -69420, test = 1e5;
//const int p[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23,  29, 31, 37};bool ck[mxn + 1];
struct Node{
    ll ab = -inf, abc = -inf, lz = -inf;
};
ll a[mxn + 5], ans[mxn + 5];
vt<pii>special[mxn + 1], queries[mxn + 1];
Node st[4 * mxn + 1];
 
void change(int nd, ll c){
    st[nd].lz = max(st[nd].lz, c);
    st[nd].abc = max(st[nd].abc, st[nd].ab + c);
}
void push(int nd){
    change(nd << 1, st[nd].lz); change(nd << 1 | 1, st[nd].lz);
    st[nd].lz = -inf;
}
void upd(int nd, int l, int r, int id, ll v){
    if(id < l || id > r)return;
    if(l == r){
        st[nd].ab = max(st[nd].ab, v);
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd].ab = max(st[nd << 1].ab, st[nd << 1 | 1].ab);
}
void updc(int nd, int l, int r, int ql, int qr, ll v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        change(nd, v);
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    updc(nd << 1, l, mid, ql, qr, v); updc(nd << 1 | 1, mid + 1, r, ql, qr, v);
    st[nd].abc = max(st[nd << 1].abc, st[nd << 1 | 1].abc);
}
ll get(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(-inf);
    if(ql <= l && qr >= r){
        return(st[nd].abc);
    }
    int mid = (l + r) >> 1;
    push(nd);
    return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
int n;
signed 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];
    deque<int>dq;
    for(int i = 1; i <= n; i++){
        while(sz(dq)){
            int j = dq.back();
            special[i * 2 - j].pb(make_pair(j, a[j] + a[i]));
            if(a[i] < a[j])break;
            dq.pop_back();
        }
        dq.pb(i);
    }
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        queries[r].pb({l, i});
    }
    for(int i = 1; i <= n; i++){
        for(auto j: special[i]){
            //cout << i << " " << j.first << ' ' << j.second << "\n";
            upd(1, 1, n, j.first, j.second);
        }
        updc(1, 1, n, 1, i, a[i]);
        for(auto [l, id]: queries[i]){
            ans[id] = get(1, 1, n, l, i);
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    return(0);
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for(auto [l, id]: queries[i]){
      |                  ^

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