oj.uz

Submission #795616

# Submission time Handle Problem Language Result Execution time Memory
795616 2023-07-27T11:46:03 Z RushB Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 138112 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[] = {(int) 1e9 + 7, (int) 1e9 + 9};
const int BASE = 37;
vector<array<int, 2>> hs[N], h[N];
int INV[2][N], lcp[N], P[2][N], n, m, H[2][N];
string L, s[N];

int inv(int x, const int MOD) {
        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 i, int l, int r) {
        int hsh = H[i][r] - (l ? H[i][l - 1] : 0);
        hsh *= INV[i][l];
        hsh %= MOD[i];
        if (hsh < 0) 
                hsh += MOD[i];
        return hsh;
}

bool check(int l, int r) {
        return binary_search(hs[r - l].begin(), hs[r - l].end(), array<int, 2>{get_hash(0, l, r), get_hash(1, l, r)});
}

void build_lcp() {
        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] = r;
        }
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        P[0][0] = P[1][0] = INV[0][0] = INV[1][0] = 1;
        FOR(j, 0, 2) {
                FOR(i, 1, N) {
                        P[j][i] = (P[j][i - 1] * BASE) % MOD[j];
                        INV[j][i] = inv(P[j][i], MOD[j]);
                }
        }
        cin >> n >> m;
        FOR(i, 0, n) {
                cin >> s[i];
                h[i].resize(s[i].size());
                h[i][0] = {s[i][0] - 'a' + 1, s[i][0] - 'a' + 1};
                FOR(k, 0, 2) {
                        FOR(j, 1, s[i].size()) {
                                h[i][j][k] = (h[i][j - 1][k] + (s[i][j] - 'a' + 1) * P[k][j] % MOD[k]) % MOD[k];
                        }
                }
                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;
        FOR(k, 0, 2) {
                H[k][0] = L[0] - 'a' + 1;
                FOR(i, 1, L.size()) {
                        H[k][i] = (H[k][i - 1] + (L[i] - 'a' + 1) * P[k][i] % MOD[k]) % MOD[k];
                }
        }
        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:37:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |                         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:62:25: note: in expansion of macro 'FOR'
   62 |                         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:75:17: note: in expansion of macro 'FOR'
   75 |                 FOR(i, 1, L.size()) {
      |                 ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 110036 KB Output is correct
2 Correct 916 ms 126464 KB Output is correct
3 Correct 924 ms 123012 KB Output is correct
4 Correct 955 ms 126696 KB Output is correct
5 Correct 949 ms 125628 KB Output is correct
6 Correct 985 ms 129172 KB Output is correct
7 Correct 971 ms 133256 KB Output is correct
8 Correct 968 ms 130184 KB Output is correct
9 Correct 957 ms 128764 KB Output is correct
10 Correct 926 ms 117144 KB Output is correct
11 Correct 936 ms 133968 KB Output is correct
12 Correct 924 ms 122660 KB Output is correct
13 Correct 935 ms 128924 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1082 ms 124220 KB Output is correct
2 Correct 1117 ms 128560 KB Output is correct
3 Correct 1068 ms 124812 KB Output is correct
4 Correct 1047 ms 121264 KB Output is correct
5 Correct 1050 ms 121544 KB Output is correct
6 Correct 1118 ms 128428 KB Output is correct
7 Correct 1145 ms 130672 KB Output is correct
8 Correct 1109 ms 126944 KB Output is correct
9 Correct 1129 ms 129400 KB Output is correct
10 Correct 1149 ms 132100 KB Output is correct
11 Correct 1088 ms 124928 KB Output is correct
12 Correct 1080 ms 124016 KB Output is correct
13 Correct 1145 ms 133432 KB Output is correct
14 Correct 1126 ms 131848 KB Output is correct
15 Correct 1022 ms 120480 KB Output is correct
16 Correct 912 ms 138112 KB Output is correct
17 Correct 881 ms 123856 KB Output is correct
18 Correct 884 ms 123596 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 110036 KB Output is correct
2 Correct 916 ms 126464 KB Output is correct
3 Correct 924 ms 123012 KB Output is correct
4 Correct 955 ms 126696 KB Output is correct
5 Correct 949 ms 125628 KB Output is correct
6 Correct 985 ms 129172 KB Output is correct
7 Correct 971 ms 133256 KB Output is correct
8 Correct 968 ms 130184 KB Output is correct
9 Correct 957 ms 128764 KB Output is correct
10 Correct 926 ms 117144 KB Output is correct
11 Correct 936 ms 133968 KB Output is correct
12 Correct 924 ms 122660 KB Output is correct
13 Correct 935 ms 128924 KB Output is correct
14 Correct 1082 ms 124220 KB Output is correct
15 Correct 1117 ms 128560 KB Output is correct
16 Correct 1068 ms 124812 KB Output is correct
17 Correct 1047 ms 121264 KB Output is correct
18 Correct 1050 ms 121544 KB Output is correct
19 Correct 1118 ms 128428 KB Output is correct
20 Correct 1145 ms 130672 KB Output is correct
21 Correct 1109 ms 126944 KB Output is correct
22 Correct 1129 ms 129400 KB Output is correct
23 Correct 1149 ms 132100 KB Output is correct
24 Correct 1088 ms 124928 KB Output is correct
25 Correct 1080 ms 124016 KB Output is correct
26 Correct 1145 ms 133432 KB Output is correct
27 Correct 1126 ms 131848 KB Output is correct
28 Correct 1022 ms 120480 KB Output is correct
29 Correct 912 ms 138112 KB Output is correct
30 Correct 881 ms 123856 KB Output is correct
31 Correct 884 ms 123596 KB Output is correct
32 Execution timed out 2061 ms 117764 KB Time limit exceeded
33 Halted 0 ms 0 KB -