oj.uz

Submission #433252

# Submission time Handle Problem Language Result Execution time Memory
433252 2021-06-19T11:00:46 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439548 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "fast-math")

using namespace std;
     
typedef long long int ll;
typedef pair<int, int> pii;
  
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
     
const int N = 3e5 + 10, MOD[] = {(int) 1e9 + 9, (int) 1e9 + 7};
struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};

int pw[2][N], H[2][N], dp[19][N], rmq[19][19][N], lg[N], n, m, q, base[] = {37, 31}; 
char S[N * 2]; 
unordered_map<pii, int, pair_hash> mp;
pii get_hash(int l, int r) {
    pii h = {(H[0][r] - 1ll * H[0][l - 1] * pw[0][r - l + 1] % MOD[0] + MOD[0]) % MOD[0], 
        (H[1][r] - 1ll * H[1][l - 1] * pw[1][r - l + 1] % MOD[1] + MOD[1]) % MOD[1]};
    return h;
}
     
void build_rmq(int id) {
    for (int i = 1; i <= n; i++) {
        rmq[id][0][i] = dp[id][i];
    }
    for (int i = 1; i < 19; i++) {
        for (int j = 1; j <= n; j++) {
            if (j + (1 << i) <= n + 1) {
                rmq[id][i][j] = max(rmq[id][i - 1][j], rmq[id][i - 1][j + (1 << (i - 1))]);
            }
        }
    }
}
     
int get_max(int id, int l, int r) {
    if (r <= l) return l;
    r = min(r, n + 1);
    int x = lg[r - l];
    return max(rmq[id][x][l], rmq[id][x][r - (1 << x)]);
}
     
int main() {
    for (int i = 2; i < N; i++) 
        lg[i] = lg[i >> 1] + 1;
    pw[0][0] = pw[1][0] = 1;
    for (int i = 1; i < N; i++) 
        for (int j : {0, 1})
            pw[j][i] = 1ll * pw[j][i - 1] * base[j] % MOD[j];
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%s", S);
        pii h = {0, 0};
        for (int j = 0; S[j]; j++) {
            h = {(1ll * h.F * base[0] % MOD[0] + S[j] - 'a' + 1) % MOD[0], 
                (1ll * h.S * base[1] % MOD[1] + S[j] - 'a' + 1) % MOD[1]};
            mp[h] = 1;
        }
    }
    scanf("%s", S + 1); m = strlen(S + 1);
    for (int i = 1; i <= m; i++) {
        for (int j : {0, 1}) 
            H[j][i] = (1ll * H[j][i - 1] * base[j] % MOD[j] + S[i] - 'a' + 1) % MOD[j];
    }
    swap(n, m);
    for (int i = 1; i <= n; i++) {
        int l = i - 1, r = n + 1;
        while (r - l > 1) {
            int md = (l + r) >> 1;
            if (mp.count(get_hash(i, md))) l = md;
            else r = md;
        }
        dp[0][i] = l + 1;
    }
    for (int j = 1; j < 19; j++) {
        build_rmq(j - 1);
        for (int i = 1; i <= n; i++) {
            dp[j][i] = get_max(j - 1, i, dp[j - 1][i] + 1);
        }
    }
    for (build_rmq(18); q; q--) {
        int l, r; scanf("%d%d", &l, &r); l++;
        int ret = 0, p = l;
        for (int i = 18; ~i; i--) {
            if (get_max(i, l, p + 1) <= r) ret += 1 << i, p = get_max(i, l, p + 1);
        }
        printf("%d\n", ret > n ? -1 : ret + 1);
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%s", S);
      |         ~~~~~^~~~~~~~~
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%s", S + 1); m = strlen(S + 1);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:91:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         int l, r; scanf("%d%d", &l, &r); l++;
      |                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 320 ms 28832 KB Output is correct
3 Correct 276 ms 21484 KB Output is correct
4 Correct 378 ms 28860 KB Output is correct
5 Correct 284 ms 24508 KB Output is correct
6 Correct 382 ms 31816 KB Output is correct
7 Correct 396 ms 34256 KB Output is correct
8 Correct 363 ms 32940 KB Output is correct
9 Correct 418 ms 30880 KB Output is correct
10 Correct 166 ms 11912 KB Output is correct
11 Correct 334 ms 32388 KB Output is correct
12 Correct 210 ms 18540 KB Output is correct
13 Correct 250 ms 24656 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 423620 KB Output is correct
2 Correct 1623 ms 430524 KB Output is correct
3 Correct 1207 ms 425884 KB Output is correct
4 Correct 833 ms 418764 KB Output is correct
5 Correct 752 ms 418568 KB Output is correct
6 Correct 1730 ms 430588 KB Output is correct
7 Correct 1851 ms 432932 KB Output is correct
8 Correct 1441 ms 428188 KB Output is correct
9 Correct 1677 ms 431340 KB Output is correct
10 Correct 1655 ms 437564 KB Output is correct
11 Correct 1278 ms 426036 KB Output is correct
12 Correct 1293 ms 423116 KB Output is correct
13 Correct 1684 ms 439464 KB Output is correct
14 Correct 1562 ms 437160 KB Output is correct
15 Correct 715 ms 416260 KB Output is correct
16 Correct 1252 ms 439548 KB Output is correct
17 Correct 781 ms 421760 KB Output is correct
18 Correct 785 ms 421436 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 320 ms 28832 KB Output is correct
3 Correct 276 ms 21484 KB Output is correct
4 Correct 378 ms 28860 KB Output is correct
5 Correct 284 ms 24508 KB Output is correct
6 Correct 382 ms 31816 KB Output is correct
7 Correct 396 ms 34256 KB Output is correct
8 Correct 363 ms 32940 KB Output is correct
9 Correct 418 ms 30880 KB Output is correct
10 Correct 166 ms 11912 KB Output is correct
11 Correct 334 ms 32388 KB Output is correct
12 Correct 210 ms 18540 KB Output is correct
13 Correct 250 ms 24656 KB Output is correct
14 Correct 1323 ms 423620 KB Output is correct
15 Correct 1623 ms 430524 KB Output is correct
16 Correct 1207 ms 425884 KB Output is correct
17 Correct 833 ms 418764 KB Output is correct
18 Correct 752 ms 418568 KB Output is correct
19 Correct 1730 ms 430588 KB Output is correct
20 Correct 1851 ms 432932 KB Output is correct
21 Correct 1441 ms 428188 KB Output is correct
22 Correct 1677 ms 431340 KB Output is correct
23 Correct 1655 ms 437564 KB Output is correct
24 Correct 1278 ms 426036 KB Output is correct
25 Correct 1293 ms 423116 KB Output is correct
26 Correct 1684 ms 439464 KB Output is correct
27 Correct 1562 ms 437160 KB Output is correct
28 Correct 715 ms 416260 KB Output is correct
29 Correct 1252 ms 439548 KB Output is correct
30 Correct 781 ms 421760 KB Output is correct
31 Correct 785 ms 421436 KB Output is correct
32 Correct 1056 ms 275076 KB Output is correct
33 Correct 1600 ms 286576 KB Output is correct
34 Correct 1674 ms 294596 KB Output is correct
35 Correct 1733 ms 289288 KB Output is correct
36 Correct 1707 ms 297688 KB Output is correct
37 Correct 1053 ms 274496 KB Output is correct
38 Execution timed out 2120 ms 439156 KB Time limit exceeded
39 Halted 0 ms 0 KB -