oj.uz

Submission #795517

# Submission time Handle Problem Language Result Execution time Memory
795517 2023-07-27T10:47:41 Z RushB Dabbeh (INOI20_dabbeh) C++17
25 / 100
 302 ms 67860 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define int int64_t
const int64_t INF = 1ll << 60;
const int N = 5e5 + 5;
const int MOD = 1e9 + 9;
const int BASE = 31;
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';
                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: 'int64_t' {aka '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: 'int64_t' {aka '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: 'int64_t' {aka '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: 'int64_t' {aka '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: 'int64_t' {aka '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 78 ms 47272 KB Output is correct
2 Correct 179 ms 57144 KB Output is correct
3 Correct 179 ms 55576 KB Output is correct
4 Correct 221 ms 57984 KB Output is correct
5 Correct 202 ms 57364 KB Output is correct
6 Correct 216 ms 59164 KB Output is correct
7 Correct 226 ms 61248 KB Output is correct
8 Correct 238 ms 59716 KB Output is correct
9 Correct 214 ms 58944 KB Output is correct
10 Correct 196 ms 52516 KB Output is correct
11 Correct 193 ms 67860 KB Output is correct
12 Correct 187 ms 58440 KB Output is correct
13 Correct 188 ms 63644 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 47272 KB Output is correct
2 Correct 179 ms 57144 KB Output is correct
3 Correct 179 ms 55576 KB Output is correct
4 Correct 221 ms 57984 KB Output is correct
5 Correct 202 ms 57364 KB Output is correct
6 Correct 216 ms 59164 KB Output is correct
7 Correct 226 ms 61248 KB Output is correct
8 Correct 238 ms 59716 KB Output is correct
9 Correct 214 ms 58944 KB Output is correct
10 Correct 196 ms 52516 KB Output is correct
11 Correct 193 ms 67860 KB Output is correct
12 Correct 187 ms 58440 KB Output is correct
13 Correct 188 ms 63644 KB Output is correct
14 Incorrect 302 ms 56160 KB Output isn't correct
15 Halted 0 ms 0 KB -