oj.uz

Submission #957725

# Submission time Handle Problem Language Result Execution time Memory
957725 2024-04-04T08:52:12 Z parlimoos Triple Jump (JOI19_jumps) C++14
100 / 100
 863 ms 102600 KB 
//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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31068 KB Output is correct
2 Correct 8 ms 31064 KB Output is correct
3 Correct 8 ms 31204 KB Output is correct
4 Correct 8 ms 31064 KB Output is correct
5 Correct 8 ms 31068 KB Output is correct
6 Correct 8 ms 31164 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 8 ms 31172 KB Output is correct
9 Correct 8 ms 31172 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31068 KB Output is correct
2 Correct 8 ms 31064 KB Output is correct
3 Correct 8 ms 31204 KB Output is correct
4 Correct 8 ms 31064 KB Output is correct
5 Correct 8 ms 31068 KB Output is correct
6 Correct 8 ms 31164 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 8 ms 31172 KB Output is correct
9 Correct 8 ms 31172 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct
11 Correct 231 ms 48856 KB Output is correct
12 Correct 226 ms 48612 KB Output is correct
13 Correct 234 ms 48732 KB Output is correct
14 Correct 224 ms 48652 KB Output is correct
15 Correct 250 ms 48628 KB Output is correct
16 Correct 232 ms 48152 KB Output is correct
17 Correct 238 ms 47864 KB Output is correct
18 Correct 228 ms 47852 KB Output is correct
19 Correct 240 ms 48720 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 50444 KB Output is correct
2 Correct 75 ms 50392 KB Output is correct
3 Correct 82 ms 51244 KB Output is correct
4 Correct 126 ms 50644 KB Output is correct
5 Correct 132 ms 50636 KB Output is correct
6 Correct 123 ms 49868 KB Output is correct
7 Correct 127 ms 49752 KB Output is correct
8 Correct 126 ms 49872 KB Output is correct
9 Correct 138 ms 50124 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31068 KB Output is correct
2 Correct 8 ms 31064 KB Output is correct
3 Correct 8 ms 31204 KB Output is correct
4 Correct 8 ms 31064 KB Output is correct
5 Correct 8 ms 31068 KB Output is correct
6 Correct 8 ms 31164 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 8 ms 31172 KB Output is correct
9 Correct 8 ms 31172 KB Output is correct
10 Correct 8 ms 31068 KB Output is correct
11 Correct 231 ms 48856 KB Output is correct
12 Correct 226 ms 48612 KB Output is correct
13 Correct 234 ms 48732 KB Output is correct
14 Correct 224 ms 48652 KB Output is correct
15 Correct 250 ms 48628 KB Output is correct
16 Correct 232 ms 48152 KB Output is correct
17 Correct 238 ms 47864 KB Output is correct
18 Correct 228 ms 47852 KB Output is correct
19 Correct 240 ms 48720 KB Output is correct
20 Correct 136 ms 50444 KB Output is correct
21 Correct 75 ms 50392 KB Output is correct
22 Correct 82 ms 51244 KB Output is correct
23 Correct 126 ms 50644 KB Output is correct
24 Correct 132 ms 50636 KB Output is correct
25 Correct 123 ms 49868 KB Output is correct
26 Correct 127 ms 49752 KB Output is correct
27 Correct 126 ms 49872 KB Output is correct
28 Correct 138 ms 50124 KB Output is correct
29 Correct 843 ms 96648 KB Output is correct
30 Correct 723 ms 96200 KB Output is correct
31 Correct 700 ms 98060 KB Output is correct
32 Correct 827 ms 96776 KB Output is correct
33 Correct 840 ms 96580 KB Output is correct
34 Correct 803 ms 94440 KB Output is correct
35 Correct 804 ms 94112 KB Output is correct
36 Correct 848 ms 93988 KB Output is correct
37 Correct 863 ms 95640 KB Output is correct
38 Correct 636 ms 102600 KB Output is correct
39 Correct 630 ms 102288 KB Output is correct
40 Correct 596 ms 99144 KB Output is correct
41 Correct 612 ms 98552 KB Output is correct
42 Correct 607 ms 98644 KB Output is correct
43 Correct 601 ms 100320 KB Output is correct
44 Correct 638 ms 101684 KB Output is correct
45 Correct 669 ms 101840 KB Output is correct
46 Correct 670 ms 98556 KB Output is correct
47 Correct 652 ms 98268 KB Output is correct
48 Correct 677 ms 98324 KB Output is correct
49 Correct 627 ms 100296 KB Output is correct
50 Correct 687 ms 99788 KB Output is correct
51 Correct 695 ms 99572 KB Output is correct
52 Correct 681 ms 97224 KB Output is correct
53 Correct 678 ms 96960 KB Output is correct
54 Correct 679 ms 96964 KB Output is correct
55 Correct 680 ms 98504 KB Output is correct