Submission #417858

#TimeUsernameProblemLanguageResultExecution timeMemory
417858codebuster_10Secret (JOI14_secret)C++17
100 / 100
519 ms4456 KiB
#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 timeMemoryGrader output
Fetching results...