oj.uz

Submission #795519

# Submission time Handle Problem Language Result Execution time Memory
795519 2023-07-27T10:48:43 Z RushB Dabbeh (INOI20_dabbeh) C++17
25 / 100
 325 ms 65416 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 + 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';
                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 87 ms 47280 KB Output is correct
2 Correct 181 ms 55348 KB Output is correct
3 Correct 205 ms 53380 KB Output is correct
4 Correct 247 ms 55464 KB Output is correct
5 Correct 212 ms 54836 KB Output is correct
6 Correct 287 ms 56520 KB Output is correct
7 Correct 258 ms 58684 KB Output is correct
8 Correct 290 ms 57152 KB Output is correct
9 Correct 281 ms 56384 KB Output is correct
10 Correct 237 ms 50372 KB Output is correct
11 Correct 267 ms 65416 KB Output is correct
12 Correct 211 ms 56212 KB Output is correct
13 Correct 249 ms 61240 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47280 KB Output is correct
2 Correct 181 ms 55348 KB Output is correct
3 Correct 205 ms 53380 KB Output is correct
4 Correct 247 ms 55464 KB Output is correct
5 Correct 212 ms 54836 KB Output is correct
6 Correct 287 ms 56520 KB Output is correct
7 Correct 258 ms 58684 KB Output is correct
8 Correct 290 ms 57152 KB Output is correct
9 Correct 281 ms 56384 KB Output is correct
10 Correct 237 ms 50372 KB Output is correct
11 Correct 267 ms 65416 KB Output is correct
12 Correct 211 ms 56212 KB Output is correct
13 Correct 249 ms 61240 KB Output is correct
14 Incorrect 325 ms 55788 KB Output isn't correct
15 Halted 0 ms 0 KB -