oj.uz

Submission #242347

# Submission time Handle Problem Language Result Execution time Memory
242347 2020-06-27T09:14:34 Z SomeoneUnknown Triple Jump (JOI19_jumps) C++14
19 / 100
 3341 ms 104064 KB 
#include <bits/stdc++.h>
using namespace std;
struct nodei{
    int lo, hi, mid, val;
    int lazyclr;
    nodei *lft, *rght;
    nodei(int l, int h){
        lo = l;
        hi = h;
        mid = (l+h)/2;
        val = 0;
        lazyclr = 0;
        if(h<l) exit(-1);
        if(l<h){
            lft = new nodei(l, mid);
            rght = new nodei(mid+1, h);
        }
    }

    void propogate(){
        //if(!lazyclr) return;
        //val = 0;
        if(lo<hi){
            lft->lazyclr += lazyclr;
            rght->lazyclr += lazyclr;
        }
        val += lazyclr;
        lazyclr = 0;
    }

    int queryf(){
        propogate();
        if(lo == hi) return lo;
        lft->propogate();
        rght->propogate();
        if(lft->val < rght->val){
            return rght->queryf();
        }else{
            return lft->queryf();
        }
    }


    int queryr(int l, int h){
        propogate();
        if(l <= lo && h >= hi) return val;
        if(l > mid) return rght->queryr(l, h);
        if(h <= mid) return lft->queryr(l, h);
        return max(lft->queryr(l, h), rght->queryr(l, h));
    }

    void update(int l, int h, int v){
        propogate();
        if(l <= lo && h >= hi){
            lazyclr += v;
            return;
        }
        if(h > mid) rght->update(l, h, v);
        if(l <= mid) lft->update(l, h, v);
        lft->propogate();
        rght->propogate();
        val = max(lft->val, rght->val);
    } //write query!
} *rootv, *rootc;
int main(){
    int n;
    scanf("%d", &n);
    rootv = new nodei(0, n-1);
    //rootc = new nodei(0, n-1);
    int firm[n];
    for(int i = 0; i < n; ++i){
        scanf("%d", &firm[i]);
        rootv->update(i, i, firm[i]);
    }
    int best[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            best[i][j] = 0;
            if(j <= i+1){
                continue;
            }
            int base = firm[i]+firm[j];
            best[i][j] = rootv->queryr(i+1, (i+j)/2)+base;
        }
    }
    for(int i = n-2; i >= 0; i--){
        for(int j = 1; j < n; j++){
            best[i][j] = max(best[i][j], best[i+1][j]);
            best[i][j] = max(best[i][j], best[i][j-1]);
        }
    }
    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++){
        int a, c;
        scanf("%d %d", &a, &c);
        a--;
        c--;
        int cbest = best[a][c];
        printf("%d\n", cbest);
    }
}

Compilation message

jumps.cpp: In function 'int main()':
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:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &firm[i]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &c);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 3300 ms 103964 KB Output is correct
12 Correct 3308 ms 103824 KB Output is correct
13 Correct 3305 ms 103900 KB Output is correct
14 Correct 3312 ms 104064 KB Output is correct
15 Correct 3323 ms 103672 KB Output is correct
16 Correct 3308 ms 103380 KB Output is correct
17 Correct 3341 ms 102992 KB Output is correct
18 Correct 3319 ms 103364 KB Output is correct
19 Correct 3306 ms 103740 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 175 ms 40192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 3300 ms 103964 KB Output is correct
12 Correct 3308 ms 103824 KB Output is correct
13 Correct 3305 ms 103900 KB Output is correct
14 Correct 3312 ms 104064 KB Output is correct
15 Correct 3323 ms 103672 KB Output is correct
16 Correct 3308 ms 103380 KB Output is correct
17 Correct 3341 ms 102992 KB Output is correct
18 Correct 3319 ms 103364 KB Output is correct
19 Correct 3306 ms 103740 KB Output is correct
20 Runtime error 175 ms 40192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -