oj.uz

Submission #677691

# Submission time Handle Problem Language Result Execution time Memory
677691 2023-01-04T07:38:45 Z Cross_Ratio Triple Jump (JOI19_jumps) C++14
19 / 100
 4000 ms 127216 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = max(seg[2*i], seg[2*i+1]);
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return max(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[500005];
int B[5005][5005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    SegTree tree(N);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) tree.seg[i+MAX/2] = A[i];
    tree.cons();
    for(int l = 0; l < N; l++) {
        for(int r = l + 2; r < N; r++) {
            B[l][r] = A[l]+A[r]+tree.sum(l+1, (l+r)/2+1, 1, 0, MAX/2);
        }
    }
    for(int len = 3; len <= N-1; len++) {
        for(i=0;i+len<=N-1;i++) {
            B[i][i+len] = max(B[i][i+len], B[i+1][i+len]);
            B[i][i+len] = max(B[i][i+len], B[i][i+len-1]);
        }
    }
    int Q;
    cin >> Q;
    while(Q--) {
        int l, r;
        cin >> l >> r;
        cout << B[l-1][r-1] << '\n';
    }
}

Compilation message

jumps.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:21:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:33:12: warning: unused variable 'j' [-Wunused-variable]
   33 |     int i, j;
      |            ^

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1448 ms 126900 KB Output is correct
12 Correct 1442 ms 127048 KB Output is correct
13 Correct 1439 ms 127012 KB Output is correct
14 Correct 1430 ms 127216 KB Output is correct
15 Correct 1466 ms 127124 KB Output is correct
16 Correct 1427 ms 126376 KB Output is correct
17 Correct 1474 ms 126504 KB Output is correct
18 Correct 1446 ms 126416 KB Output is correct
19 Correct 1496 ms 127168 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4082 ms 13768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1448 ms 126900 KB Output is correct
12 Correct 1442 ms 127048 KB Output is correct
13 Correct 1439 ms 127012 KB Output is correct
14 Correct 1430 ms 127216 KB Output is correct
15 Correct 1466 ms 127124 KB Output is correct
16 Correct 1427 ms 126376 KB Output is correct
17 Correct 1474 ms 126504 KB Output is correct
18 Correct 1446 ms 126416 KB Output is correct
19 Correct 1496 ms 127168 KB Output is correct
20 Execution timed out 4082 ms 13768 KB Time limit exceeded
21 Halted 0 ms 0 KB -