oj.uz

Submission #795328

# Submission time Handle Problem Language Result Execution time Memory
795328 2023-07-27T08:24:03 Z MISM06 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 60484 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;
int dp[N];

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';
    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) {
            int x = ask(j + 1, min(j + a[j], r + 1)) + 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:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int j = 0; j < t[i].sze; j++) {
      |                           ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 765 ms 32076 KB Output is correct
3 Execution timed out 2048 ms 31988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 32936 KB Output is correct
2 Correct 1085 ms 35240 KB Output is correct
3 Correct 983 ms 33288 KB Output is correct
4 Correct 876 ms 31644 KB Output is correct
5 Correct 912 ms 31624 KB Output is correct
6 Correct 874 ms 35208 KB Output is correct
7 Correct 915 ms 36368 KB Output is correct
8 Correct 888 ms 34360 KB Output is correct
9 Correct 924 ms 35696 KB Output is correct
10 Correct 939 ms 36792 KB Output is correct
11 Correct 956 ms 33292 KB Output is correct
12 Correct 1036 ms 32752 KB Output is correct
13 Correct 1111 ms 37312 KB Output is correct
14 Correct 1095 ms 36404 KB Output is correct
15 Correct 820 ms 31212 KB Output is correct
16 Runtime error 53 ms 60484 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 19028 KB Output is correct
2 Correct 765 ms 32076 KB Output is correct
3 Execution timed out 2048 ms 31988 KB Time limit exceeded
4 Halted 0 ms 0 KB -