oj.uz

Submission #403731

# Submission time Handle Problem Language Result Execution time Memory
403731 2021-05-13T11:48:38 Z CSQ31 Secret (JOI14_secret) C++14
100 / 100
 574 ms 4524 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2500 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2588 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 2600 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 512 ms 4420 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 504 ms 4420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 514 ms 4520 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 508 ms 4500 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 518 ms 4524 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 574 ms 4408 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 516 ms 4488 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1