| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1002170 | Huseyn123 | Dabbeh (INOI20_dabbeh) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")//#define int ll#define MAX 1000001#define INF INT_MAX#define MOD 1000000007#define mp make_pair#define mt make_tuple#define pb push_back#define ins insert#define ff first#define ss second #define all(a) a.begin(),a.end()#define lb(a,b) lower_bound(all(a),b)#define ub(a,b) upper_bound(all(a),b)#define sortv(a) sort(all(a))#define outputar(a,b){\ for(int i=0;i<b;i++){\ cout << a[i] << " ";\ }\ cout << endl;\}#define outputvec(a){\ for(auto x:a){\ cout << (int)x << " ";\ }\ cout << endl;\}#define reset(a,n,v){\ for(int i=0;i<n;i++){\ a[i]=v;\ }\}using namespace std;typedef long long ll;typedef unsigned long long ull;typedef tuple<ll,ll,ll> tll;typedef pair<ll,ll> pll;typedef pair<int,int> pii;typedef double db;typedef long double ldb;inline void USACO(string filename){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout);}int n,q,t=1,m,k,x,y,z,x2,y2,z2,d[MAX],e[MAX];long long a[MAX],b[MAX];mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());string s[MAX],str[MAX];//int e[1001][1001];string s1,s2,s3;const int mod = 998244353;int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0};int B1=133,B2=135,M1=1e9+7,M2=1e9+9; long long pow1[MAX],pow2[MAX];int cost[501][501],can[501][501];int get_hash_1(int l,int r){ long long h=a[r]; if(l!=0){ h-=a[l-1]; } if(h<0){ h+=M1; } h*=pow1[l]; h%=M1; return h;}int get_hash_2(int l,int r){ long long h=b[r]; if(l!=0){ h-=b[l-1]; } if(h<0){ h+=M2; } h*=pow2[l]; h%=M2; return h;}int N=500000;vector<vector<int>> sp(20,vector<int>(300001));struct segtree{ int size; vector<ll> maximum; void build(vector<int> &a,int x,int lx,int rx){ if(rx-lx==1){ if(lx<(int)a.size()){ maximum[x]=a[lx]; } return; } int m=(lx+rx)/2; build(a,2*x+1,lx,m); build(a,2*x+2,m,rx); maximum[x]=max(maximum[2*x+1],maximum[2*x+2]); } void build(vector<int> &a){ build(a,0,0,size); } void init(int n){ size=1; while(size<n){ size*=2; } maximum.assign(2*size,-INF); } ll get_min(int l,int r,int x,int lx,int rx){ if(lx>=r || rx<=l){ return -INF; } if(lx>=l && rx<=r){ return maximum[x]; } ll s1,s2; int m=(lx+rx)/2; s1=get_min(l,r,2*x+1,lx,m); s2=get_min(l,r,2*x+2,m,rx); return max(s1,s2); } ll get_min(int l,int r){ return get_min(l,r,0,0,size); } void set(int i,int v,int x,int lx,int rx){ if(rx-lx==1){ maximum[x]=v; return; } int m=(lx+rx)/2; if(i<m){ set(i,v,2*x+1,lx,m); } else{ set(i,v,2*x+2,m,rx); } maximum[x]=max(maximum[2*x+1],maximum[2*x+2]); } void set(int i,int v){ set(i,v,0,0,size); }};segtree st[20];void solve(){ cin >> n >> q; long long p1,p2; p1=p2=1; pow1[0]=pow2[0]=1; for(int i=1;i<=N;i++){ p1=p1*B1; p2=p2*B2; p1%=M1; p2%=M2; pow1[i]=p1; pow2[i]=p2; } unordered_map<array<ll,3>,ll> c; for(int i=0;i<n;i++){ cin >> s[i]; k=(int)s[i].size(); long long h1,h2; h1=h2=0; for(int j=0;j<k;j++){ h1+=(s[i][j]*pow1[N-j])%M1; h1%=M1; h2+=(s[i][j]*pow2[N-j])%M2; h2%=M2; c[{h1,h2,j+1}]++; } } cin >> s1; m=(int)s1.size(); long long h1,h2; h1=h2=0; for(int j=0;j<m;j++){ h1+=(s1[j]*pow1[N-j])%M1; h1%=M1; h2+=(s1[j]*pow2[N-j])%M2; h2%=M2; a[j]=h1; b[j]=h2; } for(int j=0;j<m;j++){ int l,r; l=j; r=m-1; while(l<r){ int mid=(l+r+1)/2; if(c[{get_hash_1(j,mid),get_hash_2(j,mid),mid-j+1}]){ l=mid; } else{ r=mid-1; } } if(c[{get_hash_1(j,l),get_hash_2(j,l),l-j+1}]){ d[j]=l; } else{ d[j]=-1; } sp[0][j]=d[j]; } st[0].init(m); st[0].build(sp[0]); for(int i=1;i<20;i++){ for(int j=0;j<m;j++){ if(sp[i-1][j]==-1){ sp[i][j]=-1; continue; } sp[i][j]=st[i-1].get_min(j,min(m,sp[i-1][j]+2)); } st[i].init(m); st[i].build(sp[i]); } for(int i=0;i<q;i++){ cin >> x >> y; y--; int x1=x; int res=0; bool ok=false,ok1=false; if(sp[19][x]<y){ ok1=true; } for(int j=19;j>=0;j--){ if(!ok){ //cout << x1 << " " << j << " " << sp[j][x] << "\n"; if(sp[j][x]<y){ res+=(1<<j); x=sp[j][x]; ok=true; } } else{ int h1=st[j].get_min(x1,min(m,x+2)); //cout << x1 << " zor" << y << " " << h1 << "\n"; if(h1<y){ res+=(1<<j); x=h1; } } } if(ok1){ res=-2; } cout << res+1 << "\n"; }}signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("input13.txt","r",stdin); //cin >> t; ll cnt1=1; while(t--){ solve(); cnt1++; }}