Submission #403731

#	Time	Username	Problem	Language	Result	Execution time	Memory
403731		CSQ31	Secret (JOI14_secret)	C++14	100 / 100	574 ms	4524 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
VII dat(20,vector<ll>(1000));
vector<ll>mask(1000);
vector<int>a(1000);
void re(int l,int r,int lev){
	//cout<<l<<" "<<r<<'\n';
	if(l == r)return;
	int m = (l+r)/2;
	dat[lev][m] = a[m];
	dat[lev][m+1] = a[m+1];
	for(int i=m-1;i>=l;i--)dat[lev][i] = Secret(a[i],dat[lev][i+1]);
	for(int i=m+2;i<=r;i++)dat[lev][i] = Secret(dat[lev][i-1],a[i]);
	for(int i=m+1;i<=r;i++)mask[i]+=(1<<lev);
	re(l,m,lev+1);
	re(m+1,r,lev+1);
	
}
void Init(int N, int A[]) {
  int n = N;
  for(int i=0;i<n;i++)a[i] = A[i];
  //for(int i=0;i<n;i++)cout<<a[i]<<" ";
 // cout<<'\n';
  re(0,n-1,0);
  //cout<<"masks: ";
  //for(int i=0;i<n;i++)cout<<mask[i]<<" ";
  //cout<<'\n';
}

int Query(int L, int R) {
 int b = mask[L]^mask[R];
 b = __builtin_ctz(b);
 
 if(L == R)return a[L];
 return Secret(dat[b][L],dat[b][R]);
}

• Subtask 1: 100 / 100