Submission #901488

#	Time	Username	Problem	Language	Result	Execution time	Memory
901488		anarch_y	Secret (JOI14_secret)	C++17	100 / 100	374 ms	4556 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define pb push_back
#define sz(x) (int)x.size()

const int id = 1e9+7;

const int MX = (1<<10);
int tab[10][MX];
vector<int> v;

int F(int x, int y){
    if(x == id) return y;
    if(y == id) return x;
    return Secret(x, y);
}

void divi(int L, int R, int lev){
    if(L == R) return;
    int M = (L+R)/2;
    int nex = lev-1;
    tab[nex][M] = v[M];
    for(int i=M-1; i>=L; i--) tab[nex][i] = F(v[i], tab[nex][i+1]);
    tab[nex][M+1] = v[M+1];
    for(int i=M+2; i<=R; i++) tab[nex][i] = F(tab[nex][i-1], v[i]);
    divi(L, M, nex);
    divi(M+1, R, nex);
}

void Init(int N, int A[]){
    v.resize(MX, id);
    for(int i=0; i<N; i++) v[i] = A[i];
    divi(0, MX-1, 10);
}

int Query(int l, int r){
    if(l == r) return v[l];
    int c = l + MX, d = r + MX;
    int lev = 31 - __builtin_clz(c^d);
    return F(tab[lev][l], tab[lev][r]);
}

• Subtask 1: 100 / 100