oj.uz

Submission #957465

# Submission time Handle Problem Language Result Execution time Memory
957465 2024-04-03T19:41:33 Z FEDIKUS Secret (JOI14_secret) C++17
100 / 100
 390 ms 4908 KB 
#include "secret.h"
#include<bits/stdc++.h>

using namespace std;

map<pair<int,int>,int> prec;

int *a;
int n;

void dc(int l,int r){
  if(l==r){
    prec[{l,l}]=a[l];
    return;
  }

  int mid=l+(r-l)/2;

  int tren=a[mid+1];
  prec[{mid+1,mid+1}]=tren;
  for(int i=mid+2;i<=r;i++){
    tren=Secret(tren,a[i]);
    prec[{mid+1,i}]=tren;
  }

  tren=a[mid];
  prec[{mid,mid}]=tren;
  for(int i=mid-1;i>=l;i--){
    tren=Secret(a[i],tren);
    prec[{i,mid}]=tren;
  }

  dc(l,mid);
  dc(mid+1,r);

}

void Init(int nn, int aa[]) {
  n=nn;
  a=aa;
  dc(0,n-1);
}

int result(int tl,int tr,int l=0,int r=n-1){
  int mid=l+(r-l)/2;
  if(tl<=mid && mid<tr){
    return Secret(prec[{tl,mid}],prec[{mid+1,tr}]);
  }else if(tr<=mid){
    return result(tl,tr,l,mid);
  }else return result(tl,tr,mid+1,r);
}

int Query(int l, int r) {
  if(l==r) return a[l];
  return result(l,r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2896 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 113 ms 2900 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 109 ms 2900 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 384 ms 4768 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 377 ms 4696 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 377 ms 4908 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 380 ms 4692 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 377 ms 4768 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 386 ms 4764 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 390 ms 4692 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1