oj.uz

Submission #433248

# Submission time Handle Problem Language Result Execution time Memory
433248 2021-06-19T10:55:07 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439584 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "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 352 ms 28832 KB Output is correct
3 Correct 247 ms 21480 KB Output is correct
4 Correct 368 ms 28876 KB Output is correct
5 Correct 289 ms 24608 KB Output is correct
6 Correct 386 ms 31716 KB Output is correct
7 Correct 416 ms 34196 KB Output is correct
8 Correct 370 ms 32960 KB Output is correct
9 Correct 363 ms 30820 KB Output is correct
10 Correct 168 ms 11968 KB Output is correct
11 Correct 345 ms 32348 KB Output is correct
12 Correct 218 ms 18572 KB Output is correct
13 Correct 273 ms 24536 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 423516 KB Output is correct
2 Correct 1676 ms 430432 KB Output is correct
3 Correct 1248 ms 425880 KB Output is correct
4 Correct 913 ms 418712 KB Output is correct
5 Correct 753 ms 418516 KB Output is correct
6 Correct 1662 ms 430572 KB Output is correct
7 Correct 1832 ms 432892 KB Output is correct
8 Correct 1445 ms 428152 KB Output is correct
9 Correct 1653 ms 431356 KB Output is correct
10 Correct 1606 ms 437552 KB Output is correct
11 Correct 1254 ms 426196 KB Output is correct
12 Correct 1310 ms 423036 KB Output is correct
13 Correct 1633 ms 439584 KB Output is correct
14 Correct 1521 ms 437188 KB Output is correct
15 Correct 661 ms 416228 KB Output is correct
16 Correct 1205 ms 439556 KB Output is correct
17 Correct 718 ms 421684 KB Output is correct
18 Correct 726 ms 421420 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 352 ms 28832 KB Output is correct
3 Correct 247 ms 21480 KB Output is correct
4 Correct 368 ms 28876 KB Output is correct
5 Correct 289 ms 24608 KB Output is correct
6 Correct 386 ms 31716 KB Output is correct
7 Correct 416 ms 34196 KB Output is correct
8 Correct 370 ms 32960 KB Output is correct
9 Correct 363 ms 30820 KB Output is correct
10 Correct 168 ms 11968 KB Output is correct
11 Correct 345 ms 32348 KB Output is correct
12 Correct 218 ms 18572 KB Output is correct
13 Correct 273 ms 24536 KB Output is correct
14 Correct 1427 ms 423516 KB Output is correct
15 Correct 1676 ms 430432 KB Output is correct
16 Correct 1248 ms 425880 KB Output is correct
17 Correct 913 ms 418712 KB Output is correct
18 Correct 753 ms 418516 KB Output is correct
19 Correct 1662 ms 430572 KB Output is correct
20 Correct 1832 ms 432892 KB Output is correct
21 Correct 1445 ms 428152 KB Output is correct
22 Correct 1653 ms 431356 KB Output is correct
23 Correct 1606 ms 437552 KB Output is correct
24 Correct 1254 ms 426196 KB Output is correct
25 Correct 1310 ms 423036 KB Output is correct
26 Correct 1633 ms 439584 KB Output is correct
27 Correct 1521 ms 437188 KB Output is correct
28 Correct 661 ms 416228 KB Output is correct
29 Correct 1205 ms 439556 KB Output is correct
30 Correct 718 ms 421684 KB Output is correct
31 Correct 726 ms 421420 KB Output is correct
32 Correct 1026 ms 275004 KB Output is correct
33 Correct 1503 ms 286588 KB Output is correct
34 Correct 1729 ms 294720 KB Output is correct
35 Correct 1734 ms 289484 KB Output is correct
36 Correct 1683 ms 297740 KB Output is correct
37 Correct 978 ms 274604 KB Output is correct
38 Execution timed out 2091 ms 439304 KB Time limit exceeded
39 Halted 0 ms 0 KB -