oj.uz

Submission #795562

# Submission time Handle Problem Language Result Execution time Memory
795562 2023-07-27T11:21:46 Z RushB Dabbeh (INOI20_dabbeh) C++17
25 / 100
 395 ms 113452 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 = 2000000357;
const int BASE = 131;
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;
                        h[i][j] %= MOD;
                        assert(h[i][j] >= 0);
                }
                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;
                H[i] %= MOD;
                assert(H[i] >= 0);
        }
        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';
        }
}

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:66:17: note: in expansion of macro 'FOR'
   66 |                 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:73:9: note: in expansion of macro 'FOR'
   73 |         FOR(i, 1, L.size()) {
      |         ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 94228 KB Output is correct
2 Correct 268 ms 103776 KB Output is correct
3 Correct 283 ms 101764 KB Output is correct
4 Correct 306 ms 103600 KB Output is correct
5 Correct 307 ms 102952 KB Output is correct
6 Correct 321 ms 104708 KB Output is correct
7 Correct 334 ms 106856 KB Output is correct
8 Correct 318 ms 105312 KB Output is correct
9 Correct 319 ms 104444 KB Output is correct
10 Correct 317 ms 98508 KB Output is correct
11 Correct 296 ms 113452 KB Output is correct
12 Correct 288 ms 104348 KB Output is correct
13 Correct 292 ms 109412 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 94228 KB Output is correct
2 Correct 268 ms 103776 KB Output is correct
3 Correct 283 ms 101764 KB Output is correct
4 Correct 306 ms 103600 KB Output is correct
5 Correct 307 ms 102952 KB Output is correct
6 Correct 321 ms 104708 KB Output is correct
7 Correct 334 ms 106856 KB Output is correct
8 Correct 318 ms 105312 KB Output is correct
9 Correct 319 ms 104444 KB Output is correct
10 Correct 317 ms 98508 KB Output is correct
11 Correct 296 ms 113452 KB Output is correct
12 Correct 288 ms 104348 KB Output is correct
13 Correct 292 ms 109412 KB Output is correct
14 Incorrect 395 ms 103060 KB Output isn't correct
15 Halted 0 ms 0 KB -