oj.uz

Submission #411493

# Submission time Handle Problem Language Result Execution time Memory
411493 2021-05-25T12:24:46 Z AlperenT Secret (JOI14_secret) C++17
0 / 100
 561 ms 4716 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){
        return Secret(tree[v].left[tree[v].m - l], tree[v].right[r - tree[v].m - 1]);
    }
    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 2648 KB Wrong Answer: Query(264, 271) - expected : 675707686, actual : 4619042.
2 Incorrect 136 ms 2608 KB Wrong Answer: Query(210, 211) - expected : 558550312, actual : 558532904.
3 Incorrect 136 ms 2560 KB Wrong Answer: Query(64, 128) - expected : 469502, actual : 537340286.
4 Incorrect 504 ms 4532 KB Wrong Answer: Query(571, 624) - expected : 309502044, actual : 309493852.
5 Incorrect 518 ms 4584 KB Wrong Answer: Query(876, 890) - expected : 899551822, actual : 362418254.
6 Incorrect 521 ms 4608 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 278446241.
7 Correct 548 ms 4612 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 561 ms 4512 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 529 ms 4552 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 546 ms 4716 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1