oj.uz

Submission #795528

# Submission time Handle Problem Language Result Execution time Memory
795528 2023-07-27T10:57:31 Z RushB Dabbeh (INOI20_dabbeh) C++17
25 / 100
 381 ms 112436 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 = 1e9 + 7;
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 156 ms 94188 KB Output is correct
2 Correct 251 ms 102528 KB Output is correct
3 Correct 252 ms 100584 KB Output is correct
4 Correct 279 ms 102560 KB Output is correct
5 Correct 280 ms 101928 KB Output is correct
6 Correct 294 ms 103680 KB Output is correct
7 Correct 324 ms 105808 KB Output is correct
8 Correct 297 ms 104296 KB Output is correct
9 Correct 293 ms 103448 KB Output is correct
10 Correct 269 ms 97432 KB Output is correct
11 Correct 266 ms 112436 KB Output is correct
12 Correct 263 ms 103208 KB Output is correct
13 Correct 262 ms 108448 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 94188 KB Output is correct
2 Correct 251 ms 102528 KB Output is correct
3 Correct 252 ms 100584 KB Output is correct
4 Correct 279 ms 102560 KB Output is correct
5 Correct 280 ms 101928 KB Output is correct
6 Correct 294 ms 103680 KB Output is correct
7 Correct 324 ms 105808 KB Output is correct
8 Correct 297 ms 104296 KB Output is correct
9 Correct 293 ms 103448 KB Output is correct
10 Correct 269 ms 97432 KB Output is correct
11 Correct 266 ms 112436 KB Output is correct
12 Correct 263 ms 103208 KB Output is correct
13 Correct 262 ms 108448 KB Output is correct
14 Incorrect 381 ms 102820 KB Output isn't correct
15 Halted 0 ms 0 KB -