Submission #916452

#	Time	Username	Problem	Language	Result	Execution time	Memory
916452		biank	Secret (JOI14_secret)	C++14	100 / 100	388 ms	4608 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)

const int MAXN = 1000;
const int MAXL = 10;

int val[MAXL][MAXN];
int n;

void build(int l, int r, int a[], int h) {
    int m = (l+r)/2;
    val[h][m] = a[m];
    if(l==r) return;
    //prefix
    val[h][m+1] = a[m+1];
    forsn(i,m+2,r+1) {
        val[h][i] = Secret(val[h][i-1], a[i]);
    }
    //suffix
    dforsn(i,l,m) {
        val[h][i] = Secret(a[i], val[h][i+1]);
    }
    build(l,m,a,h+1);
    build(m+1,r,a,h+1);
}

void Init(int N, int a[]) {
    n=N;
    build(0,n-1,a,0);
}

int solve(int l, int r, int a, int b, int h) {
    if(l==r) return val[h][a];
    int m=(l+r)/2;
    if(b<=m) return solve(l,m,a,b,h+1);
    if(a>=m+1) return solve(m+1,r,a,b,h+1);
    return Secret(val[h][a], val[h][b]);
}

int Query(int L, int R) {
    return solve(0,n-1,L,R,0);
}

• Subtask 1: 100 / 100