oj.uz

Submission #823462

# Submission time Handle Problem Language Result Execution time Memory
823462 2023-08-12T14:25:37 Z Cookie Triple Jump (JOI19_jumps) C++14
19 / 100
 1471 ms 524288 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);
    }
    */
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            special[j * 2 - i].pb(make_pair(i, a[i] + a[j]));
        }
    }
    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:108:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         for(auto [l, id]: queries[i]){
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 10 ms 23912 KB Output is correct
3 Correct 12 ms 23852 KB Output is correct
4 Correct 11 ms 23888 KB Output is correct
5 Correct 10 ms 23896 KB Output is correct
6 Correct 11 ms 23804 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 13 ms 23864 KB Output is correct
9 Correct 11 ms 23836 KB Output is correct
10 Correct 11 ms 23892 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 10 ms 23912 KB Output is correct
3 Correct 12 ms 23852 KB Output is correct
4 Correct 11 ms 23888 KB Output is correct
5 Correct 10 ms 23896 KB Output is correct
6 Correct 11 ms 23804 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 13 ms 23864 KB Output is correct
9 Correct 11 ms 23836 KB Output is correct
10 Correct 11 ms 23892 KB Output is correct
11 Correct 1316 ms 179148 KB Output is correct
12 Correct 1368 ms 179060 KB Output is correct
13 Correct 1411 ms 179032 KB Output is correct
14 Correct 1380 ms 179092 KB Output is correct
15 Correct 1408 ms 179132 KB Output is correct
16 Correct 1358 ms 178476 KB Output is correct
17 Correct 1330 ms 178440 KB Output is correct
18 Correct 1326 ms 178316 KB Output is correct
19 Correct 1471 ms 179012 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1170 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 10 ms 23912 KB Output is correct
3 Correct 12 ms 23852 KB Output is correct
4 Correct 11 ms 23888 KB Output is correct
5 Correct 10 ms 23896 KB Output is correct
6 Correct 11 ms 23804 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 13 ms 23864 KB Output is correct
9 Correct 11 ms 23836 KB Output is correct
10 Correct 11 ms 23892 KB Output is correct
11 Correct 1316 ms 179148 KB Output is correct
12 Correct 1368 ms 179060 KB Output is correct
13 Correct 1411 ms 179032 KB Output is correct
14 Correct 1380 ms 179092 KB Output is correct
15 Correct 1408 ms 179132 KB Output is correct
16 Correct 1358 ms 178476 KB Output is correct
17 Correct 1330 ms 178440 KB Output is correct
18 Correct 1326 ms 178316 KB Output is correct
19 Correct 1471 ms 179012 KB Output is correct
20 Runtime error 1170 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -