oj.uz

Submission #795537

# Submission time Handle Problem Language Result Execution time Memory
795537 2023-07-27T11:03:24 Z RushB Dabbeh (INOI20_dabbeh) C++17
25 / 100
 379 ms 112200 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define int long long
const int64_t INF = 1ll << 60;
const int N = 1e6 + 5;
const int MOD = 999119999;
const int BASE = 29;
vector<int> hs[N], h[N];
int H[N], INV[N], lcp[N], P[N], n, m;
string L, s[N];

int inv(int x) {
        int re = 1;
        for (int b = MOD - 2; b; b >>= 1, x = x * x % MOD) if (b & 1)
                re = re * x % MOD;
        return re;
}

int get_hash(int l, int r) {
        int hsh = H[r] - (l ? H[l - 1] : 0);
        hsh *= INV[l];
        hsh %= MOD;
        if (hsh < 0) 
                hsh += MOD;
        return hsh;
}

bool check(int l, int r) {
        return binary_search(hs[r - l].begin(), hs[r - l].end(), get_hash(l, r));
}

void build_lcp() {
        FOR(i, 0, L.size())
                lcp[i] = i + 1;
        FOR(i, 0, L.size()) {
                int l = i - 1, r = L.size();
                while (r - l > 1) {
                        int m = l + r >> 1;
                        if (check(i, m)) 
                                l = m;
                        else
                                r = m;
                }
                lcp[i] = l + 1;
        }
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        P[0] = INV[0] = 1;
        FOR(i, 1, N) {
                P[i] = (P[i - 1] * BASE) % MOD;
                INV[i] = inv(P[i]);
        }
        cin >> n >> m;
        FOR(i, 0, n) {
                cin >> s[i];
                h[i].resize(s[i].size());
                h[i][0] = s[i][0] - 'a' + 1;
                FOR(j, 1, s[i].size()) 
                        h[i][j] = (h[i][j - 1] + (s[i][j] - 'a' + 1) * P[j] % MOD) % MOD;
                FOR(j, 0, s[i].size()) {
                        hs[j].push_back(h[i][j]);
                }
        }
        FOR(i, 0, N)
                sort(hs[i].begin(), hs[i].end());
        cin >> L;
        H[0] = L[0] - 'a' + 1;
        FOR(i, 1, L.size()) {
                H[i] = (H[i - 1] + (L[i] - 'a' + 1) * P[i] % MOD) % MOD;
        }
        build_lcp();

        FOR(i, 0, m) {
                int l, r;
                cin >> l >> r;
                int ans = 0, mx = l, R = l;
                FOR(i, l, r) {
                        if (R < i)
                                break;
                        mx = max(mx, lcp[i]);
                        if (R == i) {
                                R = mx;
                                ans++;
                        }
                }
                if (R < r) {
                        cout << -1 << '\n';
                        assert(mx < r);
                }
                else
                        cout << ans << '\n';
        }
}
//13:00:40

Compilation message

Main.cpp: In function 'void build_lcp()':
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:34:9: note: in expansion of macro 'FOR'
   34 |         FOR(i, 0, L.size())
      |         ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:36:9: note: in expansion of macro 'FOR'
   36 |         FOR(i, 0, L.size()) {
      |         ^~~
Main.cpp:39:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |                         int m = l + r >> 1;
      |                                 ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:61:17: note: in expansion of macro 'FOR'
   61 |                 FOR(j, 1, s[i].size())
      |                 ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:63:17: note: in expansion of macro 'FOR'
   63 |                 FOR(j, 0, s[i].size()) {
      |                 ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:71:9: note: in expansion of macro 'FOR'
   71 |         FOR(i, 1, L.size()) {
      |         ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 94212 KB Output is correct
2 Correct 240 ms 102416 KB Output is correct
3 Correct 256 ms 100404 KB Output is correct
4 Correct 306 ms 102568 KB Output is correct
5 Correct 279 ms 101692 KB Output is correct
6 Correct 291 ms 103348 KB Output is correct
7 Correct 306 ms 105536 KB Output is correct
8 Correct 311 ms 104028 KB Output is correct
9 Correct 307 ms 103144 KB Output is correct
10 Correct 291 ms 97192 KB Output is correct
11 Correct 271 ms 112200 KB Output is correct
12 Correct 260 ms 103044 KB Output is correct
13 Correct 265 ms 108128 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 379 ms 102624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 94212 KB Output is correct
2 Correct 240 ms 102416 KB Output is correct
3 Correct 256 ms 100404 KB Output is correct
4 Correct 306 ms 102568 KB Output is correct
5 Correct 279 ms 101692 KB Output is correct
6 Correct 291 ms 103348 KB Output is correct
7 Correct 306 ms 105536 KB Output is correct
8 Correct 311 ms 104028 KB Output is correct
9 Correct 307 ms 103144 KB Output is correct
10 Correct 291 ms 97192 KB Output is correct
11 Correct 271 ms 112200 KB Output is correct
12 Correct 260 ms 103044 KB Output is correct
13 Correct 265 ms 108128 KB Output is correct
14 Incorrect 379 ms 102624 KB Output isn't correct
15 Halted 0 ms 0 KB -