Submission #468886

#	Time	Username	Problem	Language	Result	Execution time	Memory
468886		amirmohammad_nezami	Dabbeh (INOI20_dabbeh)	C++14	50 / 100	2075 ms	25952 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define lc 2 * v
#define rc 2 * v + 1
#define mid (s + e) / 2
#define PB push_back
#define ll long long 
#define ld long double
#define _sz(e) (int)e.size()
#define pii pair <int , int>
#define _all(e) e.begin() , e.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0);

const ll maxn = 3e5 + 4 , N = 1e4 + 4 , base = 307 , mod = 1e9 + 7 , INF = 1e9;

ll pbase[maxn];
int n , m , SZ , res[maxn] , dp[maxn] , pos[maxn] , seg[4 * maxn];
string t[N];
vector <ll> h[N];
vector <pii> q[maxn];

void pre() {
    pbase[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        pbase[i] = (pbase[i - 1] * base) % mod;
    }
    for (int i = 0; i <= n; ++i) {
        h[i].PB(0);
        for (int j = 1; j <= _sz(t[i]); ++j) {
            int val = (h[i].back() * base + t[i][j - 1]) % mod;
            h[i].PB(val);
        }
    }
}

inline int HASH(int i , int l , int r) {
    return (h[i][r] - (h[i][l] * pbase[r - l] % mod) + mod) % mod;
}

inline int LCP(int x , int i) {
    if(t[0][x] != t[i][0]) return 0;
    int l = 1 , r = min(SZ - x , _sz(t[i])) + 1;
    while(l < r - 1) {
        int mm = (l + r) / 2;
        if(HASH(0 , x , x + mm) == HASH(i , 0 , mm)) l = mm;
        else r = mm;
    }
    return l;
}

inline bool check(int x , int i) {
    int lcp = LCP(x , i);
    if(x + lcp == SZ) return (_sz(t[i]) > lcp);
    if(_sz(t[i]) == lcp) return 0;
    return t[0][x + lcp] < t[i][lcp];
}

inline int bs(int x) {
    if(check(x , 1)) return 1;
    int l = 1 , r = n + 1;
    while(l < r - 1) {
        int mm = (l + r) / 2;
        if(check(x , mm)) r = mm;
        else l = mm;
    }
    return r;
}

void add(int p , int x , int v = 1 , int s = 0 , int e = SZ) {
    seg[v] = min(seg[v] , x);
    if(e - s == 1) return ;
    if(p < mid) {
        add(p , x , lc , s , mid); 
        return ;
    }
    add(p , x , rc , mid , e);
}

int get(int l , int r , int v = 1 , int s = 0 , int e = SZ) {
    if(l >= e || s >= r) return INF;
    if(l <= s && e <= r) return seg[v];
    return min(get(l , r , lc , s , mid) , get(l , r , rc , mid , e));
}

int main() {
    FAST;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    cin >> t[0];
    sort(t + 1 , t + 1 + n);
    for (int i = 0; i < m; ++i) {
        int l , r; cin >> l >> r; r--;
        q[r].PB({l , i});
    }
    pre();

    SZ = _sz(t[0]);
    for (int i = 0; i < SZ; ++i) {
        pos[i] = bs(i);
        if(_sz(q[i])) {
            fill(seg , seg + 4 * SZ , INF);
            fill(dp , dp + SZ , INF);
            for (int j = i; j >= 0; --j) {
                int mx = 0;
                if(pos[j] <= n) mx = max(mx , LCP(j , pos[j]));
                if(pos[j] > 0) mx = max(mx , LCP(j , pos[j] - 1));
                dp[j] = (mx >= i - j + 1 ? 1 : get(j + 1 , j + mx + 1) + 1);
                add(j , dp[j]);
            }
            for (auto x : q[i]) {
                res[x.S] = dp[x.F];
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << (res[i] >= INF ? -1 : res[i]) << '\n';
    }
}

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