oj.uz

Submission #795341

# Submission time Handle Problem Language Result Execution time Memory
795341 2023-07-27T08:29:24 Z MISM06 Dabbeh (INOI20_dabbeh) C++14
0 / 100
 2000 ms 59788 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) {
            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: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 11 ms 19028 KB Output is correct
2 Correct 767 ms 30244 KB Output is correct
3 Execution timed out 2080 ms 30068 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 36460 KB Output is correct
2 Correct 1199 ms 38748 KB Output is correct
3 Correct 1018 ms 36852 KB Output is correct
4 Correct 898 ms 35304 KB Output is correct
5 Correct 961 ms 35392 KB Output is correct
6 Correct 905 ms 38820 KB Output is correct
7 Correct 922 ms 39812 KB Output is correct
8 Correct 880 ms 38152 KB Output is correct
9 Correct 895 ms 39108 KB Output is correct
10 Correct 951 ms 40312 KB Output is correct
11 Correct 968 ms 36868 KB Output is correct
12 Correct 1028 ms 36384 KB Output is correct
13 Correct 1083 ms 40644 KB Output is correct
14 Correct 1086 ms 39944 KB Output is correct
15 Correct 799 ms 34904 KB Output is correct
16 Runtime error 46 ms 59788 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 11 ms 19028 KB Output is correct
2 Correct 767 ms 30244 KB Output is correct
3 Execution timed out 2080 ms 30068 KB Time limit exceeded
4 Halted 0 ms 0 KB -