oj.uz

Submission #433271

# Submission time Handle Problem Language Result Execution time Memory
433271 2021-06-19T11:28:33 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 441048 KB 
#include <bits/stdc++.h>

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() {
  	mp.max_load_factor(.5), mp.reserve(1 << 4);
    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 307 ms 30392 KB Output is correct
3 Correct 272 ms 25888 KB Output is correct
4 Correct 294 ms 30332 KB Output is correct
5 Correct 299 ms 29112 KB Output is correct
6 Correct 333 ms 33220 KB Output is correct
7 Correct 371 ms 46412 KB Output is correct
8 Correct 348 ms 34472 KB Output is correct
9 Correct 305 ms 32452 KB Output is correct
10 Correct 182 ms 12236 KB Output is correct
11 Correct 289 ms 33824 KB Output is correct
12 Correct 196 ms 19180 KB Output is correct
13 Correct 257 ms 28940 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1229 ms 425716 KB Output is correct
2 Correct 1390 ms 434720 KB Output is correct
3 Correct 1249 ms 426656 KB Output is correct
4 Correct 835 ms 419904 KB Output is correct
5 Correct 812 ms 419712 KB Output is correct
6 Correct 1412 ms 435052 KB Output is correct
7 Correct 1509 ms 437232 KB Output is correct
8 Correct 1310 ms 432404 KB Output is correct
9 Correct 1381 ms 435612 KB Output is correct
10 Correct 1574 ms 439208 KB Output is correct
11 Correct 1289 ms 426900 KB Output is correct
12 Correct 1167 ms 425228 KB Output is correct
13 Correct 1621 ms 440984 KB Output is correct
14 Correct 1562 ms 438668 KB Output is correct
15 Correct 650 ms 416744 KB Output is correct
16 Correct 1414 ms 441048 KB Output is correct
17 Correct 869 ms 423928 KB Output is correct
18 Correct 865 ms 423596 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 307 ms 30392 KB Output is correct
3 Correct 272 ms 25888 KB Output is correct
4 Correct 294 ms 30332 KB Output is correct
5 Correct 299 ms 29112 KB Output is correct
6 Correct 333 ms 33220 KB Output is correct
7 Correct 371 ms 46412 KB Output is correct
8 Correct 348 ms 34472 KB Output is correct
9 Correct 305 ms 32452 KB Output is correct
10 Correct 182 ms 12236 KB Output is correct
11 Correct 289 ms 33824 KB Output is correct
12 Correct 196 ms 19180 KB Output is correct
13 Correct 257 ms 28940 KB Output is correct
14 Correct 1229 ms 425716 KB Output is correct
15 Correct 1390 ms 434720 KB Output is correct
16 Correct 1249 ms 426656 KB Output is correct
17 Correct 835 ms 419904 KB Output is correct
18 Correct 812 ms 419712 KB Output is correct
19 Correct 1412 ms 435052 KB Output is correct
20 Correct 1509 ms 437232 KB Output is correct
21 Correct 1310 ms 432404 KB Output is correct
22 Correct 1381 ms 435612 KB Output is correct
23 Correct 1574 ms 439208 KB Output is correct
24 Correct 1289 ms 426900 KB Output is correct
25 Correct 1167 ms 425228 KB Output is correct
26 Correct 1621 ms 440984 KB Output is correct
27 Correct 1562 ms 438668 KB Output is correct
28 Correct 650 ms 416744 KB Output is correct
29 Correct 1414 ms 441048 KB Output is correct
30 Correct 869 ms 423928 KB Output is correct
31 Correct 865 ms 423596 KB Output is correct
32 Correct 1174 ms 276016 KB Output is correct
33 Correct 1541 ms 290916 KB Output is correct
34 Correct 1727 ms 296164 KB Output is correct
35 Correct 1710 ms 293632 KB Output is correct
36 Correct 1806 ms 299304 KB Output is correct
37 Correct 1114 ms 274828 KB Output is correct
38 Execution timed out 2075 ms 440484 KB Time limit exceeded
39 Halted 0 ms 0 KB -