oj.uz

Submission #795346

# Submission time Handle Problem Language Result Execution time Memory
795346 2023-07-27T08:30:38 Z MISM06 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 59812 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) {
    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 781 ms 30252 KB Output is correct
3 Execution timed out 2084 ms 30080 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 36496 KB Output is correct
2 Correct 1075 ms 38704 KB Output is correct
3 Correct 952 ms 36800 KB Output is correct
4 Correct 853 ms 35396 KB Output is correct
5 Correct 912 ms 35488 KB Output is correct
6 Correct 861 ms 38824 KB Output is correct
7 Correct 890 ms 39756 KB Output is correct
8 Correct 892 ms 37944 KB Output is correct
9 Correct 884 ms 39076 KB Output is correct
10 Correct 932 ms 40380 KB Output is correct
11 Correct 961 ms 36872 KB Output is correct
12 Correct 1032 ms 36532 KB Output is correct
13 Correct 1108 ms 40592 KB Output is correct
14 Correct 1052 ms 39928 KB Output is correct
15 Correct 814 ms 34912 KB Output is correct
16 Runtime error 44 ms 59812 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 781 ms 30252 KB Output is correct
3 Execution timed out 2084 ms 30080 KB Time limit exceeded
4 Halted 0 ms 0 KB -