oj.uz

Submission #557813

# Submission time Handle Problem Language Result Execution time Memory
557813 2022-05-06T05:07:07 Z Kaipalo Secret (JOI14_secret) C++14
100 / 100
 502 ms 8360 KB 
#include "secret.h"
#include <iostream>

using namespace std;

int n;
int cal[1005][1005];

void build(int l, int r, int A[]) {
    int mid = (l + r) / 2;
    cal[mid][mid] = A[mid];
    cal[mid+1][mid+1] = A[mid+1];
    for (int i = mid-1; i >= l; i--) cal[i][mid] = Secret(A[i], cal[i+1][mid]);
    for (int i = mid+2; i <= r; i++) cal[mid+1][i] = Secret(cal[mid+1][i-1], A[i]);

    if (l < mid) build(l, mid, A);
    if (mid+1 < r) build(mid+1, r, A);
}

int query(int wantL, int wantR, int l = 0, int r = n-1) {
    int mid = (l + r) / 2;
    if (l == r) return cal[l][r];
    if (wantL <= mid && wantR > mid)
        return Secret( cal[wantL][mid], cal[mid+1][wantR] );

    if (wantL > mid) return query(wantL, wantR, mid+1, r);
    else return query(wantL, wantR, l, mid);
}


void Init(int N, int A[]) {
    n = N;
    build(0, n-1, A);
}

int Query(int L, int R) {
    return query(L, R);
}

/*
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
ans:
13
32
8
13
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4356 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 136 ms 4384 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 129 ms 4480 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 468 ms 8284 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 440 ms 8228 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 486 ms 8260 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 451 ms 8228 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 479 ms 8304 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 451 ms 8280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 502 ms 8360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1