Submission #401535

#TimeUsernameProblemLanguageResultExecution timeMemory
401535NhatMinh0208Brperm (RMI20_brperm)C++14
100 / 100
2526 ms123636 KiB
/* Normie's Template v2.2 Changes: Added modulo binpow and inverse. */ // Standard library in one include. #include <bits/stdc++.h> using namespace std; // ordered_set library. #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update> // AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.) //#include <atcoder/all> //using namespace atcoder; //Pragmas (Comment out these three lines if you're submitting in szkopul.) #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast,unroll-loops,tree-vectorize") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") //File I/O. #define FILE_IN "cseq.inp" #define FILE_OUT "cseq.out" #define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout) //Fast I/O. #define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define nfio cin.tie(0);cout.tie(0) #define endl "\n" //Order checking. #define ord(a,b,c) ((a>=b)and(b>=c)) //min/max redefines, so i dont have to resolve annoying compile errors. #define min(a,b) (((a)<(b))?(a):(b)) #define max(a,b) (((a)>(b))?(a):(b)) // Fast min/max assigns to use with AVX. // Requires g++ 9.2.0. template<typename T> __attribute__((always_inline)) void chkmin(T& a, const T& b) { a=(a<b)?a:b; } template<typename T> __attribute__((always_inline)) void chkmax(T& a, const T& b) { a=(a>b)?a:b; } //Constants. #define MOD (ll(998244353)) #define MAX 300001 #define mag 320 const long double PI=3.14159265358979; //Pairs and 3-pairs. #define p1 first #define p2 second.first #define p3 second.second #define fi first #define se second #define pii(element_type) pair<element_type,element_type> #define piii(element_type) pair<element_type,pii(element_type)> //Quick power of 2. #define pow2(x) (ll(1)<<x) //Short for-loops. #define ff(i,__,___) for(int i=__;i<=___;i++) #define rr(i,__,___) for(int i=__;i>=___;i--) //Typedefs. #define bi BigInt typedef long long ll; typedef long double ld; typedef short sh; // Binpow and stuff ll BOW(ll a, ll x, ll p) { if (!x) return 1; ll res=BOW(a,x/2,p); res*=res; res%=p; if (x%2) res*=a; return res%p; } ll INV(ll a, ll p) { return BOW(a,p-2,p); } //---------END-------// random_device rd; mt19937 rng(rd()); int p,base; int prime(ll x) { if (x<2) return 0; for (int i=2;i<=sqrt(x);i++) if (x%i==0) return 0; return 1; } ll get_rand(ll l, ll r) { return uniform_int_distribution<ll>(l,r)(rng); } ll get_p() { ll res; while(true) { res=get_rand(1e9,1e9+4e8); if (prime(res)) return res; } } vector<int> vec; ll N,m,i,j,k,t,t1,u,v,a,b; ll pr,ba; char c[500001]; int bf[500001][20]; int af[500001][20]; int af2[500001][20]; int pw[500001]; int ipw[500001]; void init(int n, const char s[]) { N=n; pr=get_p(); ba=get_rand(27,pr-1); // cout<<pr<<' '<<ba<<endl; memcpy(c,s,n); pw[0]=ipw[0]=1; pw[1]=ba; ipw[1]=INV(ba,pr); for (i=2;i<=n;i++) { pw[i]=((ll)pw[i-1]*pw[1])%pr; ipw[i]=((ll)ipw[i-1]*ipw[1])%pr; } for (i=0;i<n;i++) bf[i][0]=c[i]-96; for (j=1;j<20;j++) { for (i=0;i+(1<<j)-1<n;i++) { u=(ll)bf[i][j-1]+(ll)bf[i+(1<<(j-1))][j-1]*pw[(1<<(j-1))]; bf[i][j]=u%pr; // cout<<i<<' '<<j<<' '<<bf[i][j]<<endl; } } for (i=0;i<n;i++) { af[i][0]=c[i]-96; } for (j=18;j>=0;j--) { for (k=0;k<20;k++) if (j+k<=22) for (i=0;i+(1<<(j+k))-(1<<j)<n;i++) { if (k==0) { af2[i][k]=c[i]-96; } else if (k==1) { u=(ll)af2[i][k-1]+(ll)af2[i+(1<<j)][k-1]*pw[(1<<j)]; af2[i][k]=u%pr; } else { u= (ll)af[i][k-2] +(ll)af[i+(1<<j)][k-2]*pw[(1<<(j+k-1))] +(ll)af[i+(1<<(j+k-1))][k-2]*pw[(1<<j)] +(ll)af[i+(1<<(j+k-1))+(1<<j)][k-2]*pw[(1<<(j+k-1))+(1<<j)]; af2[i][k]=u%pr; } // cout<<i<<' '<<j<<' '<<k<<' '<<af2[i][k]<<endl; } for (k=0;k<20;k++) if (j+k<=22) for (i=0;i+(1<<(j+k))-(1<<j)<n;i++) { af[i][k]=af2[i][k]; } } } int query(int i, int k) { if (i+(1<<k)>N) return 0; return (bf[i][k]==af[i][k]); }

Compilation message (stderr)

brperm.cpp:22: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   22 | #pragma comment(linker, "/stack:200000000")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...