oj.uz

Submission #411496

# Submission time Handle Problem Language Result Execution time Memory
411496 2021-05-25T12:31:25 Z AlperenT Secret (JOI14_secret) C++17
100 / 100
 582 ms 4620 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

const int N = 1e3 + 5;

int arr[N], n;

struct Item{
    int m;
    vector<int> left, right;
};

Item tree[N * 4];

void build(int v, int l, int r){
    if(l == r) tree[v] = {l, {arr[l]}, {}};
    else{
        int m = l + (r - l) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);

        int curval = arr[m];
        tree[v] = {m, {arr[m]}, {}};

        for(int i = m - 1; i >= l; i--){
            curval = Secret(arr[i], curval);
            tree[v].left.push_back(curval);
        }

        curval = arr[m + 1];

        if(m + 1 <= r) tree[v].right.push_back(curval);

        for(int i = m + 2; i <= r; i++){
            curval = Secret(curval, arr[i]);
            tree[v].right.push_back(curval);
        }
    }
}

int doquery(int v, int tl, int tr, int l, int r){
    if(l >= tl && r <= tr && tree[v].m >= l && tree[v].m <= r){
        if(r - tree[v].m - 1 >= 0){
            return Secret(tree[v].left[tree[v].m - l], tree[v].right[r - tree[v].m - 1]);
        }
        else return tree[v].left[tree[v].m - l];
    }
    else{
        int tm = tl + (tr - tl) / 2;
        if(r <= tm) return doquery(v * 2, tl, tm, l, r);
        else return doquery(v * 2 + 1, tm + 1, tr, l, r);
    }
}

void Init(int nn, int a[]) {
    n = nn;

    for(int i = 0; i < n; i++) arr[i] = a[i];

    build(1, 0, n - 1);
}

int Query(int l, int r) {
    return doquery(1, 0, n - 1, l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2560 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 2668 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 2628 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 517 ms 4528 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 523 ms 4556 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 522 ms 4620 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 522 ms 4512 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 527 ms 4584 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 582 ms 4576 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 548 ms 4544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1