Submission #367228

#	Time	Username	Problem	Language	Result	Execution time	Memory
367228		uacoder123	Secret (JOI14_secret)	C++14	100 / 100	515 ms	12396 KiB

secret

#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 / 100