oj.uz

Submission #200925

# Submission time Handle Problem Language Result Execution time Memory
200925 2020-02-08T15:10:56 Z mhy908 Triple Jump (JOI19_jumps) C++14
100 / 100
 1178 ms 52688 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, q;
LL arr[500010], ans[500010];
pair<pii, int> query[500010];
vector<pii> poss;
int stck[500010], re;
struct SEGMENT_TREE{
    int x;
    struct NODE{
        LL f, arr, ans;
        NODE operator+(NODE a){
            return {max(f, a.f), max(arr, a.arr), max(max(ans, a.ans), f+a.arr)};
        }
    }tree[2000000];
    void update_arr(int point, int s, int e, int num, LL qu){
        if(s==e){
            tree[point].arr=qu;
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        int mid=(s+e)>>1;
        if(num<=mid)update_arr(point*2, s, mid, num, qu);
        else update_arr(point*2+1, mid+1, e, num, qu);
        tree[point]=tree[point*2]+tree[point*2+1];
    }
    void update_f(int point, int s, int e, int num, LL qu){
        if(s==e){
            tree[point].f=max(tree[point].f, qu);
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        int mid=(s+e)>>1;
        if(num<=mid)update_f(point*2, s, mid, num, qu);
        else update_f(point*2+1, mid+1, e, num, qu);
        tree[point]=tree[point*2]+tree[point*2+1];
    }
    NODE query(int point, int s, int e, int a, int b){
        if(s>=a&&e<=b)return tree[point];
        if(s>b||e<a)return {-llinf, -llinf, -llinf};
        int mid=(s+e)>>1;
        return query(point*2, s, mid, a, b)+query(point*2+1, mid+1, e, a, b);
    }
    LL query(int a, int b){
        return query(1, 1, n, a, b).ans;
    }
}seg;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
        seg.update_arr(1, 1, n, i, arr[i]);
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &query[i].F.F, &query[i].F.S);
        query[i].S=i;
    }
    for(int i=1; i<=n; i++){
        while(re&&arr[stck[re]]<=arr[i]){
            poss.pb(mp(stck[re--], i));
        }
        if(re){
            poss.pb(mp(stck[re], i));
        }
        stck[++re]=i;
    }
    sort(all(poss), greater<pii>());
    sort(query+1, query+q+1, greater<pair<pii, int> >());
    int pv=0;
    for(int i=1; i<=q; i++){
        while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
            if(poss[pv].S*2-poss[pv].F<=n){
                seg.update_f(1, 1, n, poss[pv].S*2-poss[pv].F, arr[poss[pv].F]+arr[poss[pv].S]);
                //printf("inserted %d %d\n", poss[pv].F, poss[pv].S);
            }
            pv++;
        }
        //printf("answered %d %d\n", query[i].F.F, query[i].F.S);
        ans[query[i].S]=seg.query(query[i].F.F, query[i].F.S);
    }
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
               ~~^~~~~~~~~~~~
jumps.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &query[i].F.F, &query[i].F.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 445 ms 16760 KB Output is correct
12 Correct 438 ms 16636 KB Output is correct
13 Correct 455 ms 16632 KB Output is correct
14 Correct 418 ms 16764 KB Output is correct
15 Correct 442 ms 16632 KB Output is correct
16 Correct 439 ms 16120 KB Output is correct
17 Correct 447 ms 16120 KB Output is correct
18 Correct 453 ms 15992 KB Output is correct
19 Correct 440 ms 16504 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 19300 KB Output is correct
2 Correct 105 ms 17128 KB Output is correct
3 Correct 105 ms 17640 KB Output is correct
4 Correct 192 ms 19172 KB Output is correct
5 Correct 189 ms 19300 KB Output is correct
6 Correct 168 ms 19172 KB Output is correct
7 Correct 167 ms 19236 KB Output is correct
8 Correct 169 ms 19172 KB Output is correct
9 Correct 171 ms 19300 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 445 ms 16760 KB Output is correct
12 Correct 438 ms 16636 KB Output is correct
13 Correct 455 ms 16632 KB Output is correct
14 Correct 418 ms 16764 KB Output is correct
15 Correct 442 ms 16632 KB Output is correct
16 Correct 439 ms 16120 KB Output is correct
17 Correct 447 ms 16120 KB Output is correct
18 Correct 453 ms 15992 KB Output is correct
19 Correct 440 ms 16504 KB Output is correct
20 Correct 180 ms 19300 KB Output is correct
21 Correct 105 ms 17128 KB Output is correct
22 Correct 105 ms 17640 KB Output is correct
23 Correct 192 ms 19172 KB Output is correct
24 Correct 189 ms 19300 KB Output is correct
25 Correct 168 ms 19172 KB Output is correct
26 Correct 167 ms 19236 KB Output is correct
27 Correct 169 ms 19172 KB Output is correct
28 Correct 171 ms 19300 KB Output is correct
29 Correct 1142 ms 52688 KB Output is correct
30 Correct 932 ms 48800 KB Output is correct
31 Correct 952 ms 50524 KB Output is correct
32 Correct 1178 ms 52620 KB Output is correct
33 Correct 1150 ms 52580 KB Output is correct
34 Correct 1124 ms 52048 KB Output is correct
35 Correct 1137 ms 51924 KB Output is correct
36 Correct 1163 ms 51792 KB Output is correct
37 Correct 1164 ms 52312 KB Output is correct
38 Correct 896 ms 52560 KB Output is correct
39 Correct 893 ms 52560 KB Output is correct
40 Correct 875 ms 50896 KB Output is correct
41 Correct 909 ms 50768 KB Output is correct
42 Correct 923 ms 50576 KB Output is correct
43 Correct 896 ms 51540 KB Output is correct
44 Correct 950 ms 52560 KB Output is correct
45 Correct 941 ms 52640 KB Output is correct
46 Correct 949 ms 51024 KB Output is correct
47 Correct 908 ms 50896 KB Output is correct
48 Correct 909 ms 50884 KB Output is correct
49 Correct 944 ms 52176 KB Output is correct
50 Correct 1039 ms 52560 KB Output is correct
51 Correct 994 ms 52688 KB Output is correct
52 Correct 975 ms 51836 KB Output is correct
53 Correct 973 ms 51672 KB Output is correct
54 Correct 967 ms 51668 KB Output is correct
55 Correct 970 ms 52560 KB Output is correct