Submission #1259123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259123		mohammadsam	Dabbeh (INOI20_dabbeh)	C++20	100 / 100	850 ms	203536 KiB

Main

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 5e5 + 10,SQ=320,LOG=22;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , m ;
int P[2];
int Inv(int x){
    return (x <= 1 ? 1 : md(-(MD/x)*Inv(MD%x)));
}
int pw[N][2],inv[N][2];
vector<pii> Hash[N];
string s;
int l;
int f[N];
int ps[N][2];
pii mx[N][LOG];
int dp[N][LOG];
inline pii gethash(int l,int r){
    pii ans;
    for(int j = 0;j < 2;j++){
        int x = ps[r][j];
        if(l) x = md(x - ps[l-1][j]);
        x = md(x * inv[l][j]);
        if(j == 0) ans.fi = x;
        else ans.sec = x;
    }
    return ans;
}
inline pii get(int l,int r){
    int ln = r - l + 1;
    ln = __lg(ln);
    // cout << ln << sep << mx[l][ln].fi << sep << r + 1 - (1<<ln) << sep << mx[r + 1 - (1<<ln)][ln].fi << endl;
    return max(mx[l][ln],mx[r + 1 - (1<<ln)][ln]);
}
bool check(int l,int r){
    pii h = gethash(l,r);
    int x = lower_bound(all(Hash[r-l+1]),h) - Hash[r-l+1].begin();
    if(x < len(Hash[r-l+1]) && Hash[r-l+1][x] == h) return 1;
    return 0;
}
int ask(int l,int r){
    int tmp = l;
    int cost = 0;
    for(int j = LOG-1;j >= 0;j--){
        if(dp[l][j] < r){
            cost += (1<<j);
            l = get(tmp,dp[l][j]).sec;
        }
    }
    if(dp[l][0] >= r) return cost + 1;
    return -1;
}
bool isprime(int x){
    if(x == 1) return 0;
    for(int j = 2;j<x;j++){
        if(x%j == 0) return 0;
    }
    return 1;
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    
   
    cin >> n >> m ;
    rng.seed(n^m);
    for(int j = 0;j < 2;j++){
        P[j] = rng()%1000 + 100;
        while(!isprime(P[j])) P[j]++;
    }
    for(int j = 0 ;j < 2;j++) pw[0][j] = inv[0][j] = 1;
    for(int i =1 ;i < N;i++){
        for(int j = 0 ;j < 2;j++){
            pw[i][j] = md(pw[i-1][j] * P[j]);
        }
    }
    for(int j = 0; j  <2;j++) inv[1][j] = Inv(P[j]);
    for(int i =2 ;i < N;i++) {
        for(int j = 0;j < 2 ;j++){
            inv[i][j] = md(inv[i-1][j] * inv[1][j]);
        }
    }
    for(int i = 1 ;i <= n;i++){
        string s;
        cin >> s;
        int hs[2] = {0,0};
        for(int j = 0; j < len(s);j++){
            for(int r = 0;r < 2;r++){
                hs[r] = md(hs[r] + md(pw[j][r] * (s[j] - 'a')));
            }
            Hash[j+1].pb(Mp(hs[0],hs[1]));
        }
    }
    for(int i = 1;i < N;i++) sort(all(Hash[i]));
    cin >> s;
    l = len(s);
    for(int j = 0; j < 2;j++) ps[0][j] = (s[0] - 'a');
    for(int i = 1;i < l;i++){
        for(int j = 0; j < 2;j++){
            ps[i][j] = md(ps[i-1][j] + md((s[i] - 'a') * pw[i][j]));
        }
    }
    for(int i = 0; i < l;i++){
        int dw = i-1,up = l;
        while(up-dw>1){
            int mid = (up + dw)>>1;
            if(check(i,mid)) dw = mid;
            else up = mid;
        }
        f[i] = up;
    }
    for(int i = l-1 ;i >= 0;i--){
        mx[i][0] = {f[i],i};
        for(int j =1 ;j < LOG && i + (1<<j) - 1 < l;j++){
            mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
   
  
    for(int i = l-1; i >= 0;i--){
        dp[i][0] = f[i];
        for(int j = 1;j < LOG;j++){
            dp[i][j] = dp[i][j-1];
            if(dp[i][j] < l){
                int R = get(i,dp[i][j]).sec;
                dp[i][j] = dp[R][j-1];
            }
        }
    }
    
    
    while(m--){
        int l,r;
        cin >> l >> r;
        cout << ask(l,r) << endl;
    }



    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50