Submission #795616

#	Time	Username	Problem	Language	Result	Execution time	Memory
795616		RushB	Dabbeh (INOI20_dabbeh)	C++17	50 / 100	2061 ms	138112 KiB

Main

#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 (stderr)

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50