oj.uz

Submission #158332

# Submission time Handle Problem Language Result Execution time Memory
158332 2019-10-16T13:35:57 Z georgerapeanu Triple Jump (JOI19_jumps) C++11
100 / 100
 1633 ms 85884 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 5e5;

int n,q;
int v[NMAX + 5];

int st[NMAX + 5],len;

vector<int> segments[NMAX + 5];
vector<pair<int,int> > queries[NMAX + 5];

int ans[NMAX + 5];

struct node_t {
    int ma_val;
    int lazy;
    int best_ans;
    int offset_min;
    int offset_max;

    node_t operator + (const node_t &other)const {
        node_t ans;
        ans.ma_val = max(this->ma_val,other.ma_val);
        ans.lazy = 0;
        ans.offset_min = min(this->offset_min,other.offset_min);
        ans.offset_max = max(this->offset_max,other.offset_max);
        ans.best_ans = max(this->best_ans,other.best_ans);
        return ans;
    }

} aint[NMAX * 4 + 5];

void propag(int nod,int st,int dr) {
    if(st == dr || aint[nod].lazy == 0) {
        return ;
    }
    aint[nod * 2].lazy = max(aint[nod * 2].lazy,aint[nod].lazy);
    aint[nod * 2 + 1].lazy = max(aint[nod * 2 + 1].lazy,aint[nod].lazy);
    aint[nod * 2].offset_min = max(aint[nod * 2].offset_min,aint[nod].lazy);
    aint[nod * 2].offset_max = max(aint[nod * 2].offset_max,aint[nod].lazy);
    aint[nod * 2 + 1].offset_min = max(aint[nod * 2 + 1].offset_min,aint[nod].lazy);
    aint[nod * 2 + 1].offset_max = max(aint[nod * 2 + 1].offset_min,aint[nod].lazy);
    aint[nod * 2].best_ans = aint[nod * 2].ma_val + aint[nod * 2].offset_max;
    aint[nod * 2 + 1].best_ans = aint[nod * 2 + 1].ma_val + aint[nod * 2 + 1].offset_max;
    aint[nod].lazy = 0;
}

void init(int nod,int st,int dr) {
    if(st == dr) {
        aint[nod].ma_val = v[st];
        aint[nod].lazy = 0;
        aint[nod].best_ans = -1;
        aint[nod].offset_min = -(1 << 28);
        aint[nod].offset_max = -(1 << 28);
        return ;
    }

    int mid = (st + dr) / 2;

    init(nod * 2,st,mid);
    init(nod * 2 + 1,mid + 1,dr);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update(int nod,int st,int dr,int l,int r,int val) {
    propag(nod,st,dr);
    if(l > dr || r < st || aint[nod].offset_min >= val) {
        return ;
    }
    if(l <= st && dr <= r && aint[nod].offset_max <= val) {
        aint[nod].lazy = val;
        aint[nod].offset_min = max(aint[nod].offset_min,val);
        aint[nod].offset_max = max(aint[nod].offset_max,val);
        aint[nod].best_ans = aint[nod].ma_val + aint[nod].offset_max;
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,l,r,val);
    update(nod * 2 + 1,mid + 1,dr,l,r,val);
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

int query(int nod,int st,int dr,int l,int r) {
    propag(nod,st,dr);

    if(l > dr || r < st) {
        return 0;
    }

    if(l <= st && dr <= r) {
        return aint[nod].best_ans;
    }

    int mid = (st + dr) / 2;

    return max(query(nod * 2,st,mid,l,r),query(nod * 2 + 1,mid + 1,dr,l,r));
}

int main() {

    scanf("%d",&n);

    for(int i = 1; i <= n; i++) {
        scanf("%d",&v[i]);
    }

    scanf("%d",&q);

    for(int i = 1; i <= q; i++) {
        int l,r;
        scanf("%d %d",&l,&r);
        queries[l].push_back({r,i});
    }


    for(int i = 1; i <= n; i++) {
        while(len > 0 && v[st[len]] < v[i]) {
            segments[st[len]].push_back(i);
            len--;
        }
        if(len > 0) {
            segments[st[len]].push_back(i);
        }
        st[++len] = i;
    }

    init(1,1,n);

    for(int i = n; i; i--) {
        for(auto it:segments[i]) {
            if(2 * it - i <= n){
                update(1,1,n,2 * it - i,n,v[i] + v[it]);
            }
        }
        for(auto it:queries[i]) {
            ans[it.second] = query(1,1,n,i,it.first);
        }
    }

    for(int i = 1; i <= q; i++) {
        printf("%d\n",ans[i]);
    }


    return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&v[i]);
         ~~~~~^~~~~~~~~~~~
jumps.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&l,&r);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23772 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23772 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 403 ms 37496 KB Output is correct
12 Correct 402 ms 37496 KB Output is correct
13 Correct 443 ms 37624 KB Output is correct
14 Correct 471 ms 37624 KB Output is correct
15 Correct 420 ms 37520 KB Output is correct
16 Correct 425 ms 36856 KB Output is correct
17 Correct 417 ms 36804 KB Output is correct
18 Correct 411 ms 36856 KB Output is correct
19 Correct 412 ms 37404 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 41336 KB Output is correct
2 Correct 158 ms 41084 KB Output is correct
3 Correct 166 ms 43640 KB Output is correct
4 Correct 280 ms 43096 KB Output is correct
5 Correct 279 ms 43000 KB Output is correct
6 Correct 280 ms 42460 KB Output is correct
7 Correct 270 ms 42388 KB Output is correct
8 Correct 269 ms 42360 KB Output is correct
9 Correct 274 ms 42616 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23804 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23772 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23800 KB Output is correct
11 Correct 403 ms 37496 KB Output is correct
12 Correct 402 ms 37496 KB Output is correct
13 Correct 443 ms 37624 KB Output is correct
14 Correct 471 ms 37624 KB Output is correct
15 Correct 420 ms 37520 KB Output is correct
16 Correct 425 ms 36856 KB Output is correct
17 Correct 417 ms 36804 KB Output is correct
18 Correct 411 ms 36856 KB Output is correct
19 Correct 412 ms 37404 KB Output is correct
20 Correct 278 ms 41336 KB Output is correct
21 Correct 158 ms 41084 KB Output is correct
22 Correct 166 ms 43640 KB Output is correct
23 Correct 280 ms 43096 KB Output is correct
24 Correct 279 ms 43000 KB Output is correct
25 Correct 280 ms 42460 KB Output is correct
26 Correct 270 ms 42388 KB Output is correct
27 Correct 269 ms 42360 KB Output is correct
28 Correct 274 ms 42616 KB Output is correct
29 Correct 1619 ms 80188 KB Output is correct
30 Correct 1191 ms 79660 KB Output is correct
31 Correct 1314 ms 81660 KB Output is correct
32 Correct 1504 ms 80212 KB Output is correct
33 Correct 1506 ms 80184 KB Output is correct
34 Correct 1513 ms 79488 KB Output is correct
35 Correct 1500 ms 79644 KB Output is correct
36 Correct 1633 ms 79428 KB Output is correct
37 Correct 1509 ms 80064 KB Output is correct
38 Correct 1153 ms 85772 KB Output is correct
39 Correct 1155 ms 85884 KB Output is correct
40 Correct 1128 ms 84240 KB Output is correct
41 Correct 1123 ms 84004 KB Output is correct
42 Correct 1121 ms 83960 KB Output is correct
43 Correct 1134 ms 84828 KB Output is correct
44 Correct 1228 ms 85268 KB Output is correct
45 Correct 1225 ms 85428 KB Output is correct
46 Correct 1202 ms 83876 KB Output is correct
47 Correct 1194 ms 83716 KB Output is correct
48 Correct 1232 ms 83604 KB Output is correct
49 Correct 1213 ms 84860 KB Output is correct
50 Correct 1319 ms 83272 KB Output is correct
51 Correct 1323 ms 83032 KB Output is correct
52 Correct 1296 ms 82376 KB Output is correct
53 Correct 1294 ms 82220 KB Output is correct
54 Correct 1322 ms 82364 KB Output is correct
55 Correct 1317 ms 82984 KB Output is correct