oj.uz

Submission #795307

# Submission time Handle Problem Language Result Execution time Memory
795307 2023-07-27T08:16:35 Z MISM06 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 60520 KB 
#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;
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[N], inv[N];
int n, m, nn;
string t[N], s;
int L[N], R[N];
int a[N];
pll h[N];
vector < pll > o;

inline pll get (int l, int r) {
    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;
}
 
int 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';
    for (int i = 1; i <= m; i++) {
        build();
        int l = L[i], r = R[i];
        upd(0, r + 1);
        for (int j = r; j >= l; --j) {
            int x = ask(j, j + a[j]) + 1;
            upd(x, j);
            // cout << j << " : " << x << '\n';
        }
        int 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

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 949 ms 32224 KB Output is correct
3 Execution timed out 2057 ms 32432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 32888 KB Output is correct
2 Correct 1129 ms 35232 KB Output is correct
3 Correct 982 ms 33180 KB Output is correct
4 Correct 924 ms 31644 KB Output is correct
5 Correct 984 ms 31708 KB Output is correct
6 Correct 895 ms 35200 KB Output is correct
7 Correct 983 ms 36360 KB Output is correct
8 Correct 974 ms 34332 KB Output is correct
9 Correct 1014 ms 35596 KB Output is correct
10 Correct 1042 ms 36860 KB Output is correct
11 Correct 1072 ms 33328 KB Output is correct
12 Correct 1153 ms 32744 KB Output is correct
13 Correct 1319 ms 37196 KB Output is correct
14 Correct 1240 ms 36512 KB Output is correct
15 Correct 934 ms 31248 KB Output is correct
16 Runtime error 46 ms 60520 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 949 ms 32224 KB Output is correct
3 Execution timed out 2057 ms 32432 KB Time limit exceeded
4 Halted 0 ms 0 KB -