oj.uz

Submission #367228

# Submission time Handle Problem Language Result Execution time Memory
367228 2021-02-16T16:21:24 Z uacoder123 Secret (JOI14_secret) C++14
100 / 100
 515 ms 12396 KB 
#include "secret.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
int pre[4*1001][1000],suf[4*1001][1000],a[1000];
void init(int node,int l,int r)
{
  int m=(l+r)/2;
  if(r-l+1==1)
    return;
  suf[node][0]=a[m];
  for(int i=1;i<=(m-l);++i)
    suf[node][i]=Secret(a[m-i],suf[node][i-1]);
  pre[node][0]=a[m+1];
  for(int i=1;i<=(r-(m+1));++i)
    pre[node][i]=Secret(pre[node][i-1],a[m+1+i]);
  init(2*node+1,l,m);
  init(2*node+2,m+1,r);

}
int no;
void Init(int N, int A[]) {
  no=N;
  for(int i=0;i<N;++i)
    a[i]=A[i];
  init(0,0,N-1);
}
int qu(int node,int l,int r,int s,int e)
{
  if(l==r)
    return a[l];
  int m=(l+r)/2;
  if(l<=s&&m>=e)
    return qu(2*node+1,l,m,s,e);
  else if(m+1<=s&&r>=e)
    return qu(2*node+2,m+1,r,s,e);
  return(Secret(suf[node][m-(s)],pre[node][e-(m+1)]));
}
int Query(int L, int R) 
{
  return qu(0,0,no-1,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 6508 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 6508 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 164 ms 6508 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 503 ms 12268 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 508 ms 12268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 515 ms 12184 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 511 ms 12232 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 514 ms 12268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 12396 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 512 ms 12396 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1