Submission #1260392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260392		mohammad86	Dabbeh (INOI20_dabbeh)	C++20	0 / 100	193 ms	10976 KiB

Main

/* @Date    : 2025-08-18 13:18:37
   @Author  : hasan_86 */
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define endl "\n"

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

vector<int> sort_cyclic_shift(string &s) {
    int n = s.size();
    vector<int> p(n), c(n), cnt(max(n, 256));

    for (int i = 0; i < n; i++) {
        cnt[s[i]]++;
    }
    for (int i = 1; i < 256; i++) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
        p[--cnt[s[i]]] = i;
    }
    int cl = 1;
    c[p[0]] = 0;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i - 1]])
            cl++;
        c[p[i]] = cl - 1;
    }

    for (int l = 0; (1 << l) < n; l++) {
        vector<int> pn(n), cn(n);

        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << l);
            if (pn[i] < 0)
                pn[i] += n;
        }

        fill(begin(cnt), begin(cnt) + cl, 0);

        for (int i = 0; i < n; i++) {
            cnt[c[pn[i]]]++;
        }
        for (int i = 1; i < cl; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            p[--cnt[c[pn[i]]]] = pn[i];
        }
        cl = 1;
        cn[p[0]] = 0;
        for (int i = 1; i < n; i++) {
            pii prv = {c[p[i - 1]], c[(p[i - 1] + (1 << l)) % n]};
            pii cur = {c[p[i]], c[(p[i] + (1 << l)) % n]};
            if (prv != cur)
                cl++;
            cn[p[i]] = cl - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> suffix_array(string &S) {
    S += '#';
    vector<int> p = sort_cyclic_shift(S);
    S.pop_back();
    p.erase(p.begin());
    return p;
}

vector<int> cal_lcp(vector<int> &p, string &S) {
    int n = S.size();
    vector<int> rank(n);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    vector<int> lcp(n - 1);
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1)
            continue;
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && S[i + k] == S[j + k])
            k++;
        lcp[rank[i]] = k; 
        if (k)
            k--;
    }
    return lcp;
}

const int maxN = 10000;
const int maxL = 1e6 + 100;
const int K = 550;
string t[maxN];
bool mark[maxL];
int arr[maxL];
int nxt[maxL];
int cnt[maxL];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    string S;
    cin >> S;
    int L = S.size();
    for (int i = 0; i < n; i++) {
        S += '$';
        mark[(int)S.size()] = true;
        S += t[i];
    }

    vector<int> p = suffix_array(S);
    vector<int> lcp = cal_lcp(p, S);
    lcp.pb(0);

    int tmp = 0;
    for (int i = 0; i < p.size(); i++) {
        if (mark[p[i]]) {
            tmp = lcp[i];
        } else {
            arr[p[i]] = tmp;
        }
        tmp = min(tmp, lcp[i]);
    }
    tmp = 0;
    for (int i = p.size() - 1; i >= 0; i--) {
        if (mark[p[i]]) {
            if (i > 0)
                tmp = lcp[i-1];
        } else {
            arr[p[i]] = max(arr[p[i]], tmp);
        }
        if (i > 0)
            tmp = min(tmp, lcp[i-1]);
    }

    for (int i = L - 1; i >= 0; i--) {
        if (arr[i] == 0) {
            nxt[i] = -1;
            continue;
        }
        int j = i + arr[i];
        if (j / K != i / K || j >= L) {
            nxt[i] = min(j, L);
            cnt[i] = 1;
        } else {
            nxt[i] = nxt[j];
            cnt[i] = cnt[j] + 1;
        }
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        r--;
        bool flag = false;
        int ans = 0;
        int gl = l / K;
        int gr = r / K;
        while (gl < gr) {
            ans += cnt[l];
            l = nxt[l];
            if (l == -1) {
                flag = true;
                break;
            }
            gl = l / K;
        }
        while (!flag && l <= r) {
            if (arr[l] == 0) {
                flag = true;
                break;
            }
            l += arr[l];
            ans++;
        }
        if (flag) {
            cout << -1 << endl;
        } else {
            cout << ans << endl;
        }
    }
}

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