Submission #1174218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174218		nguyenkhangninh99	Secret (JOI14_secret)	C++17	100 / 100	342 ms	4488 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

const int maxn = 1e3 + 5;
int n, a[maxn], st0[11][maxn], st1[11][maxn];

void build(int id, int l, int r){
    if(l == r) return;
    
    int m = (l + r) / 2;
    st0[id][m] = a[m];
    st1[id][m + 1] = a[m + 1];
    for (int i = m - 1; i >= l; i--) st0[id][i] = Secret(a[i], st0[id][i + 1]);
    for (int i = m + 2; i <= r; i++) st1[id][i] = Secret(st1[id][i - 1], a[i]);
    
    build(id + 1, l, m);
    build(id + 1, m + 1, r);
    return;
}

void Init (int N, int A[]){
    n = N;
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
    
    build(1, 1, n);
    return;
}

int Query(int L, int R){
    L++; R++;
    if (L == R) return a[L];
    
    int l = 1, r = n, id = 0; 

    while(true){
        id++;
        int m = (l + r) / 2;
        if(L <= m && m < R) break;
        if(m >= R) r = m;
        else l = m + 1;
    }
    return Secret(st0[id][L], st1[id][R]);
}

• Subtask 1: 100 / 100