Submission #703303

#	Time	Username	Problem	Language	Result	Execution time	Memory
703303		bane	Secret (JOI14_secret)	C++17	100 / 100	447 ms	4580 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
typedef long long ll;
const int MAX = 10005;

ll arr[MAX], ret[40][MAX], mask[MAX];
int n;
void init(int l, int r, int lvl = 0){
	if (l == r) {
        ret[lvl][l] = arr[l];
        return;
    }
    int m = (l + r) >> 1;
    ret[lvl][m] = arr[m];
    for (int i = m - 1; i >= l; i--) ret[lvl][i] = Secret(arr[i], ret[lvl][i + 1]);
    ret[lvl][m + 1] = arr[m + 1];
    for (int i = m + 2; i <= r; i++) ret[lvl][i] = Secret(ret[lvl][i - 1], arr[i]);
    init(l, m, lvl+1);
    init(m + 1, r, lvl+1);
}
int get(int l, int r, int lvl, int L, int R){
	if (l == r)return ret[lvl][l];
	int m = (l + r) / 2;
	if (R<=m)return get(l,m,lvl+1,L,R);
	else if (L > m)return get(m+1,r,lvl+1,L,R);
	else return Secret(ret[lvl][L], ret[lvl][R]);
}
void Init(int N_, int A[]) {
	n = N_;
	for (int i = 0; i  < n; ++i)arr[i] = A[i];
	
	init(0,n-1,0);
}

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

• Subtask 1: 100 / 100