Submission #795849

#	Time	Username	Problem	Language	Result	Execution time	Memory
795849		MISM06	Dabbeh (INOI20_dabbeh)	C++14	25 / 100	2060 ms	41036 KiB

Main

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

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < int , pii > piii;
typedef pair < ll , ll > pll;
typedef pair < ll , pll > plll;
#define pb  push_back
#define all(x)  x.begin(), x.end()
#define sze     size()
#define F   first
#define S   second
#define kids    int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define wall__ cout << "________________________________________\n";

const ll p = 727, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
const ll N = 3e5 + 10, M = 5e5 + 10;
const ll inf = 1e9 + 10;

inline void add (pll &x, pll y) {
    x = {(x.F + y.F + mod1) % mod1, (x.S + y.S + mod2) % mod2};
}
inline pll Sum (pll x, pll y) {
    return {(x.F + y.F + mod1) % mod1, (x.S + y.S + mod2) % mod2};
}
inline pll mul (pll x, pll y) {
    return {x.F * y.F % mod1, x.S * y.S % mod2};
} 
inline ll pw (ll x, ll y, ll mod) {
    ll res = 1;
    while(y) {
        if (y & 1) res = x * res % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
pll pp[M], inv[M];
int n, m, nn;
string t[N], s;
int L[N], R[N];
int a[N];
pll h[N];
vector < pll > o;
int dp[N];

inline pll get (int l, int r) {
    r = min(r, n);
    return mul(inv[l - 1], Sum(h[r], {-h[l - 1].F, -h[l - 1].S}));
}
bool find (pll x) {
    auto it = lower_bound(all(o), x);
    if (it == o.end()) return 0;
    pll y = *it;
    if (y.F == x.F && y.S == x.S) return 1;
    return 0;
}
 
ll seg[N << 2];
void build (int v = 1, int tl = 1, int tr = n + 1) {
    if (tl == tr) {
        seg[v] = inf;
        return;
    } kids;
    build(cl, tl, mid);
    build(cr, mid + 1, tr);
    seg[v] = inf;
}
void upd (int val, int pos, int v = 1, int tl = 1, int tr = n + 1) {
    if (tl == tr) {
        seg[v] = val;
        return;
    } kids;
    if (pos <= mid) upd(val, pos, cl, tl, mid);
    else upd(val, pos, cr, mid + 1, tr);
    seg[v] = min(seg[cl], seg[cr]);
}
int ask (int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
    if (l > r) return inf;
    if (l == tl && r == tr) return seg[v];
    kids;
    return min(ask(l, min(r, mid), cl, tl, mid), ask(max(l, mid + 1), r, cr, mid + 1, tr));
}

void solve () {
    cin >> nn >> m;
    for (int i = 1; i <= nn; i++) cin >> t[i];
    cin >> s; n = s.sze;
    h[0] = {0, 0};
    for (int i = 1; i <= n; i++) h[i] = Sum(h[i - 1], mul(pp[i], {s[i - 1], s[i - 1]}));
    for (int i = 1; i <= m; i++) {
        cin >> L[i] >> R[i];
        ++L[i];
    }
    for (int i = 1; i <= nn; i++) {
        pll x = {0, 0};
        for (int j = 0; j < t[i].sze; j++) {
            x = Sum(x, mul(pp[j + 1], {t[i][j], t[i][j]}));
            o.pb(x);
        }
    }
    sort(all(o));
    // cout << "* " << find(get(4, 5)) << '\n';
    // pll x = get(4, 5);
    // cout << "** " << x.F << " , " << x.S << '\n';
    // for (auto e : o) {
    //     cout << e.F << "," << e.S << " | ";
    // }
    // cout << '\n';
    for (int i = 1; i <= n; i++) {
        if (!find(get(i, i))) continue;
        int l = 1, r = n - i + 2, mid;
        while(r - l > 1) {
            mid = (l + r) / 2;
            if (find(get(i, i + mid - 1))) l = mid;
            else r = mid;
        }
        a[i] = l;
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << a[i] << " ";
    // }
    // cout << '\n';
    build();
    for (int i = 1; i <= m; i++) {
        int l = L[i], r = R[i];
        upd(0, r + 1);
        for (int j = r; j >= l; --j) {
            ll x = ask(j + 1, min(j + a[j], r + 1)) + 1;
            upd(x, j);
            // cout << j << " : " << x << '\n';
        }
        ll res = ask(l, l);
        // cout << l << " , " << r << " = ";
        if (res >= inf) cout << -1 << '\n';
        else cout << res << '\n';
        // wall__
    }
}

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

    pp[0] = {1, 1};
    for(int i = 1; i < N; i++) pp[i] = mul(pp[i - 1], {p, p});
    inv[N - 1] = {pw(pp[N - 1].F, mod1 - 2, mod1), pw(pp[N - 1].S, mod2 - 2, mod2)};
    for (int i = N - 2; i >= 0; --i) inv[i] = mul(inv[i + 1], {p, p});

    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int j = 0; j < t[i].sze; j++) {
      |                           ^

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