Submission #1122197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122197		Hamed_Ghaffari	Dabbeh (INOI20_dabbeh)	C++17	100 / 100	925 ms	83896 KiB

Main

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

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())
#define Mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 5e5+5, MXL = 3e5+5, LOG = 20;

ll mod[2] = {1000000007, 998244353}, p[2][MXN];

bool is_prime(int x) {
    for(int i=2; i*i<=x; i++)
        if(x%i == 0)
            return 0;
    return 1;
}
void generate() {
    for(int t : {0, 1}) {
        p[t][0] = 1;
        p[t][1] = rng()%50 + 100;
        while(p[0][1]==p[1][1] || !is_prime(p[t][1])) p[t][1]++;
        for(int i=2; i<MXN; i++) p[t][i] = p[t][i-1]*p[t][1]%mod[t];
    }
}
ll h[2][MXN];
void init(string s) {
    for(int t : {0, 1})
        for(int i=1; i<=SZ(s); i++)
            h[t][i] = (h[t][i-1]*p[t][1]+s[i-1])%mod[t];
}
pll geth(int l, int r) {
    return Mp(
        (h[0][r-1] - h[0][l-1]*p[0][r-l]%mod[0] + mod[0])%mod[0],
        (h[1][r-1] - h[1][l-1]*p[1][r-l]%mod[1] + mod[1])%mod[1]
    );
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};

int n, m, L, nxt[MXL], par[LOG][MXL];
string s;
unordered_map<pll,bool,pair_hash> hashs;

pii seg[MXL<<2];
void Build(int l=0, int r=L+1, int id=1) {
    if(r-l == 1) {
        seg[id] = Mp(nxt[l], l);
        return;
    }
    Build(l, mid, lc);
    Build(mid, r, rc);
    seg[id] = max(seg[lc], seg[rc]);
}
pii Get(int s, int e, int l=0, int r=L+1, int id=1) {
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return Get(s, e, l, mid, lc);
    if(s>=mid) return Get(s, e, mid, r, rc);
    return max(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    generate();
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> s;
        init(s);
        for(int i=1; i<=SZ(s); i++)
            hashs[geth(1, i+1)]=1;
    }
    cin >> s;
    init(s);
    L = SZ(s);
    for(int i=0; i<L; i++) {
        int l=i-1, r=L;
        while(r-l>1)
            if(hashs.find(geth(i+1, mid+2)) != hashs.end()) l = mid;
            else r = mid;
        nxt[i] = l+1;
    }
    nxt[L] = L;
    Build();
    for(int i=0; i<=L; i++) {
        int p = Get(i, nxt[i]+1).Y;
        par[0][i] = (p == i ? L+1 : p);
    }
    par[0][L+1] = L+1;
    for(int i=1; i<LOG; i++)
        for(int j=0; j<=L+1; j++)
            par[i][j] = par[i-1][par[i-1][j]];
    while(m--) {
        int L, R;
        cin >> L >> R;
        // cout << "-1\n";
        int ans=0, v=L;
        for(int i=LOG-1; i>=0; i--)
            if(par[i][v] < R) {
                ans += 1<<i;
                v = par[i][v];
            }
        if(nxt[v]<R) {
            cout << "-1\n";
            continue;
        }
        if(ans == 0) {
            cout << "1\n";
            continue;
        }
        int d = ans-1;
        v = L;
        for(int i=0; i<LOG; i++)
            if(d>>i & 1)
                v = par[i][v];
        cout << ans + (nxt[v]<R) << '\n';
    }
    return 0;
}

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