oj.uz

Submission #1018610

# Submission time Handle Problem Language Result Execution time Memory
1018610 2024-07-10T07:25:29 Z dosts Secret (JOI14_secret) C++17
100 / 100
 318 ms 4688 KB 
#include "secret.h"
#include <bits/stdc++.h>
//Dost SEFEROĞLU
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;


int dat[10][1001];
int mask[1001];
int B[1001];

void dnc(int l,int r,int level = 0) {
  if (l == r) return;
  int m = (l+r) >> 1;
  dat[level][m] = B[m];
  for (int i=m-1;i>=l;i--) dat[level][i] = Secret(B[i],dat[level][i+1]);
  dat[level][m+1] = B[m+1];
  for (int i=m+2;i<=r;i++) dat[level][i] = Secret(dat[level][i-1],B[i]);
  for (int i=m+1;i<=r;i++) mask[i]^=(1<<level);
  dnc(l,m,level+1),dnc(m+1,r,level+1);
}

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

int32_t Query(int32_t L, int32_t R) {
  L++;
  R++;
  if (L == R) return B[L];
  int tz = __builtin_ctz(mask[L]^mask[R]);
  return Secret(dat[tz][L],dat[tz][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2752 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 86 ms 2648 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 96 ms 2736 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 306 ms 4500 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 307 ms 4372 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 318 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 290 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 307 ms 4688 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 308 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 315 ms 4284 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1