oj.uz

Submission #538901

# Submission time Handle Problem Language Result Execution time Memory
538901 2022-03-18T02:10:57 Z schiftyfive4 Secret (JOI14_secret) C++14
100 / 100
 485 ms 4444 KB 
#include <bits/stdc++.h>
#include "secret.h"
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1e3+5;
const int STALA=30;
int t[MAX][STALA];
int n;
int a[MAX];
void rec1(int l,int r,int dep){
  if (l>r)return;
  int mid=(l+r)>>1;
  t[mid][dep]=a[mid];
  t[mid+1][dep]=a[mid+1];
  for (int i=mid-1;i>=l;i--){
    t[i][dep]=Secret(a[i],t[i+1][dep]);
  }
  
  for (int i=mid+2;i<=r;i++){
    t[i][dep]=Secret(t[i-1][dep],a[i]);
  } 
  if (l<r){
    rec1(l,mid,dep+1);
    rec1(mid+1,r,dep+1);
  }
}
 
void Init(int N,int A[]){
  n=N;
  for (int i=0;i<n;i++)a[i]=A[i];
  rec1(0,n-1,0);
}
 
int rec2(int l,int r,int L,int R,int dep){
  int mid=(l+r)>>1;
  if (L>mid)return rec2(mid+1,r,L,R,dep+1);
  if (R<=mid)return rec2(l,mid,L,R,dep+1);
  return Secret(t[L][dep],t[R][dep]);
} 
 
int Query(int L,int R){
  if (L==R)return a[L];
  return rec2(0,n-1,L,R,0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 2384 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 2336 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 141 ms 2552 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 439 ms 4396 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 447 ms 4444 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 466 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 469 ms 4368 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 457 ms 4336 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 485 ms 4376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 454 ms 4340 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1