Submission #823454

# Submission time Handle Problem Language Result Execution time Memory
823454 2023-08-12T14:22:37 Z Cookie Triple Jump (JOI19_jumps) C++14
0 / 100
143 ms 45636 KB
#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;
    dq.pb(n);
    for(int i = n - 1; i >= 1; i--){
        for(int j = 0; j < sz(dq); j++){
            special[2 * dq[j] - i].pb(make_pair(i, a[i] + a[dq[j]]));
        }
        while(sz(dq) && a[dq.back()] <= a[i])dq.pop_back();
        if(i && a[i - 1] <= a[i]){
            while(sz(dq))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

jumps.cpp: In function 'int main()':
jumps.cpp:101:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |         for(auto [l, id]: queries[i]){
      |                  ^
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 10 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 10 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 45636 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 10 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -