#include "secret.h"
#include <bits/stdc++.h>
using namespace std ;
//#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
#ifdef ONLINE_JUDGE
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define __f(...) 0
#endif
}
/**
* Description: Range queries for any associative operation on static array
* If you get TLE, try declaring everything globally.
* Time: O(n log n) build, O(1) query
* Source: Benq
* Verification: https://www.codechef.com/viewsolution/47401581
*/
template<class T> struct static_range_query {
int N;
const T ID = -1;
vector<vector<T>> store; // comb(ID,x) = x.
vector<T> a;
T comb (T a, T b) { // associative operation.
if(a == ID) return b;
if(b == ID) return a;
else return Secret(a,b);
}
void fill(int l, int r, int ind) {
if (ind < 1) return;
int m = (l+r)/2 ;
T val = ID;
for(int i = m-1; i >= l; --i){
store[i][ind] = val = comb(a[i],val);
}
val = ID;
for(int i = m; i < r; ++i){
store[i][ind] = val = comb(val,a[i]);
}
fill(l,m,ind-1);
fill(m,r,ind-1);
}
void init(const vector<T> _a) {
a = _a;
for(N = 1; (1<<N) < int(a.size()); ++N);
store = vector<vector<int>> (1<<N,vector<int>(N,ID));
while(sz(a) < (1<<N)) a.pb(ID);
fill(0,(1<<N),N-1);
}
T query(int l, int r) {
if(l + 1 == r) return comb(a[l],a[r]);
if (l == r) return a[l];
int level = 31 - __builtin_clz(r^l);
return comb(store[l][level], store[r][level]);
}
};
static_range_query<int> srq;
vt<int> a;
void Init(int n,int b[]){
f(i,0,n) a.pb(b[i]);
srq.init(a);
return;
}
int Query(int L, int R){
return srq.query(L,R);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
2312 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
142 ms |
2356 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
142 ms |
2356 KB |
Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
504 ms |
4280 KB |
Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
519 ms |
4376 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
503 ms |
4432 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
511 ms |
4324 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
519 ms |
4456 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
507 ms |
4320 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
508 ms |
4292 KB |
Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1 |
