oj.uz

Submission #373387

# Submission time Handle Problem Language Result Execution time Memory
373387 2021-03-04T12:03:57 Z wind_reaper Secret (JOI14_secret) C++17
100 / 100
 542 ms 4588 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

const int MXN = 1005;

int st[10][MXN], mask[MXN], a[MXN], n;

void dnc(int l, int r, int lev){
	if(l == r)
		return;

	int mid = (l+r)>>1;

	st[lev][mid] = a[mid];
	st[lev][mid+1] = a[mid+1];

	for(int i = mid-1; i >= l; --i)
		st[lev][i] = Secret(a[i], st[lev][i+1]);

	for(int i = mid+2; i <= r; i++)
		st[lev][i] = Secret(st[lev][i-1], a[i]);

	for(int i = mid+1; i <= r; i++)
		mask[i] ^= (1 << lev);

	dnc(l, mid, lev+1), dnc(mid+1, r, lev+1);
}

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

int Query(int L, int R){
	if(L == R)
		return a[L];
	int level = __builtin_ctz(mask[L]^mask[R]);
	return Secret(st[level][L], st[level][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 2520 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 156 ms 2540 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 2540 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 520 ms 4464 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 509 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 506 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 542 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 505 ms 4452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 506 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 502 ms 4480 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1