oj.uz

Submission #540789

# Submission time Handle Problem Language Result Execution time Memory
540789 2022-03-21T17:56:45 Z xuliu Secret (JOI14_secret) C++17
100 / 100
 453 ms 4348 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int N = 1e3, M = 10;
int dat[M][N], mask[N];
vector<int> x;

void sx(int l, int r, int lev) {
	if(l == r) return;
	int m = (l+r)/2;
	dat[lev][m] = x[m]; dat[lev][m+1] = x[m+1];
	for(int i=m-1; i>=l; i--) dat[lev][i] = Secret(x[i], dat[lev][i+1]);
	for(int i=m+2; i<=r; i++) dat[lev][i] = Secret(dat[lev][i-1], x[i]);
	for(int i=m+1; i<=r; i++) mask[i] ^= (1<<lev);
	sx(l, m, lev+1); sx(m+1, r, lev+1);
}

void Init(int n, int A[]) {
	x.assign(n, 0);
	for(int i=0; i<n; i++) x[i] = A[i];
	sx(0, n-1, 0);
}

int Query(int l, int r) {
	if(l == r) return x[l];
	int bb = __builtin_ctz(mask[l]^mask[r]);
	return Secret(dat[bb][l], dat[bb][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2388 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 128 ms 2408 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 123 ms 2476 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 452 ms 4320 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 429 ms 4316 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 452 ms 4320 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 443 ms 4284 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 441 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 453 ms 4276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 453 ms 4212 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1