oj.uz

Submission #636538

# Submission time Handle Problem Language Result Execution time Memory
636538 2022-08-29T13:35:23 Z JooDdae Secret (JOI14_secret) C++17
100 / 100
 424 ms 4556 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
 
#define mid ((l+r) >> 1)
 
int n, a[1010];
vector<int> LL[4040], RR[4040];
 
void build(int node = 1, int l = 1, int r = n) {
    if(l > r) return;
 
    LL[node].push_back(a[mid]);
    for(int i=mid-1;i>=l;i--) {
        LL[node].push_back(Secret(a[i], LL[node].back()));
    }
 
    if(l == r) return;
 
    RR[node].push_back(a[mid+1]);
    for(int i=mid+2;i<=r;i++) {
        RR[node].push_back(Secret(RR[node].back(), a[i]));
    }
 
    build(node*2, l, mid-1), build(node*2+1, mid+1, r);
}
 
void Init(int N, int A[]) {
    n = N;
    for(int i=1;i<=n;i++) a[i] = A[i-1];
    build();
}
 
 
int find(int nl, int nr, int node = 1, int l = 1, int r = n) {
    if(nl <= mid && mid <= nr) {
        if(mid == nr) return LL[node][mid-nl];
        return Secret(LL[node][mid-nl], RR[node][nr-mid-1]);
    }
 
    if(nr < mid) return find(nl, nr, node*2, l, mid-1);
    return find(nl, nr, node*2+1, mid+1, r);
}
 
int Query(int L, int R) {
    return find(L+1, R+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 2672 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 120 ms 2596 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 118 ms 2728 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 421 ms 4428 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 418 ms 4468 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 416 ms 4520 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 424 ms 4520 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 423 ms 4556 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 416 ms 4456 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 423 ms 4476 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1