oj.uz

답안 #755260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
755260 2023-06-09T16:19:47 Z penguin133 비밀 (JOI14_secret) C++17
100 / 100
 523 ms 4436 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include "secret.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int a[1030], n, sp[12][1030], cnt;
void Init(int N, int A[]) {
	n = N;
  for(int i=0;i<n;i++)a[i] = A[i];
  while((1 << cnt) < n)cnt++;
  n = (1 << cnt);
  for(int i = 0; i < cnt; i++){
	  int blk = (1 << i);
	  int sz = (n + blk - 1) / blk;
	  for(int j = 1; j <= blk; j++){
		  int lb = (j - 1) * sz, ub = min(n - 1, j * sz - 1);
		  if(lb >= N)break;
		  int mid = (lb + ub) >> 1;
		  for(int k = mid; k >= lb; k--){
            if(k >= N)continue;
			  if(k == mid || k == N - 1)sp[i][k] = a[k];
			  else sp[i][k] = Secret(a[k], sp[i][k + 1]);
		  }
		  for(int k = mid + 1; k <= min(N - 1, ub); k++){
			  if(k == mid + 1)sp[i][k] = a[k];
			  else sp[i][k] = Secret(sp[i][k-1], a[k]);
		  }
	  }
  }
}
 
int Query(int L, int R) {
  if(L == R)return a[L];
  int brr = L ^ R;
  brr = cnt - (31 - __builtin_clz(brr)) - 1;
  return Secret(sp[brr][L], sp[brr][R]);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 2316 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 122 ms 2344 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 132 ms 2400 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 523 ms 4436 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 492 ms 4384 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 441 ms 4240 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 466 ms 4296 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 447 ms 4380 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 426 ms 4300 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 430 ms 4288 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1