oj.uz

Submission #433268

# Submission time Handle Problem Language Result Execution time Memory
433268 2021-06-19T11:26:23 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439672 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")

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(.6), 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:2:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops")
      |                                                               ^
Main.cpp:2:63: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:16:52: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   16 |     size_t operator () (const std::pair<T1,T2> &p) const {
      |                                                    ^~~~~
Main.cpp:16:52: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:26:26: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   26 | pii get_hash(int l, int r) {
      |                          ^
Main.cpp:26:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:32:22: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   32 | void build_rmq(int id) {
      |                      ^
Main.cpp:32:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:45:33: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   45 | int get_max(int id, int l, int r) {
      |                                 ^
Main.cpp:45:33: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:52:10: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
   52 | int main() {
      |          ^
Main.cpp:52:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp: In function 'int main()':
Main.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%s", S);
      |         ~~~~~^~~~~~~~~
Main.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%s", S + 1); m = strlen(S + 1);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:92:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         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 290 ms 28832 KB Output is correct
3 Correct 257 ms 24472 KB Output is correct
4 Correct 334 ms 28876 KB Output is correct
5 Correct 278 ms 27472 KB Output is correct
6 Correct 339 ms 31800 KB Output is correct
7 Correct 409 ms 40948 KB Output is correct
8 Correct 368 ms 40800 KB Output is correct
9 Correct 331 ms 30896 KB Output is correct
10 Correct 179 ms 11988 KB Output is correct
11 Correct 357 ms 41232 KB Output is correct
12 Correct 191 ms 18540 KB Output is correct
13 Correct 263 ms 27456 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 424836 KB Output is correct
2 Correct 1646 ms 433456 KB Output is correct
3 Correct 1464 ms 425836 KB Output is correct
4 Correct 863 ms 419452 KB Output is correct
5 Correct 856 ms 419184 KB Output is correct
6 Correct 1677 ms 433624 KB Output is correct
7 Correct 1865 ms 435812 KB Output is correct
8 Correct 1574 ms 431024 KB Output is correct
9 Correct 1724 ms 434160 KB Output is correct
10 Correct 1857 ms 437620 KB Output is correct
11 Correct 1487 ms 425988 KB Output is correct
12 Correct 1295 ms 424588 KB Output is correct
13 Correct 1910 ms 439532 KB Output is correct
14 Correct 1787 ms 437376 KB Output is correct
15 Correct 652 ms 416632 KB Output is correct
16 Correct 1350 ms 439672 KB Output is correct
17 Correct 808 ms 423056 KB Output is correct
18 Correct 811 ms 422824 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 290 ms 28832 KB Output is correct
3 Correct 257 ms 24472 KB Output is correct
4 Correct 334 ms 28876 KB Output is correct
5 Correct 278 ms 27472 KB Output is correct
6 Correct 339 ms 31800 KB Output is correct
7 Correct 409 ms 40948 KB Output is correct
8 Correct 368 ms 40800 KB Output is correct
9 Correct 331 ms 30896 KB Output is correct
10 Correct 179 ms 11988 KB Output is correct
11 Correct 357 ms 41232 KB Output is correct
12 Correct 191 ms 18540 KB Output is correct
13 Correct 263 ms 27456 KB Output is correct
14 Correct 1436 ms 424836 KB Output is correct
15 Correct 1646 ms 433456 KB Output is correct
16 Correct 1464 ms 425836 KB Output is correct
17 Correct 863 ms 419452 KB Output is correct
18 Correct 856 ms 419184 KB Output is correct
19 Correct 1677 ms 433624 KB Output is correct
20 Correct 1865 ms 435812 KB Output is correct
21 Correct 1574 ms 431024 KB Output is correct
22 Correct 1724 ms 434160 KB Output is correct
23 Correct 1857 ms 437620 KB Output is correct
24 Correct 1487 ms 425988 KB Output is correct
25 Correct 1295 ms 424588 KB Output is correct
26 Correct 1910 ms 439532 KB Output is correct
27 Correct 1787 ms 437376 KB Output is correct
28 Correct 652 ms 416632 KB Output is correct
29 Correct 1350 ms 439672 KB Output is correct
30 Correct 808 ms 423056 KB Output is correct
31 Correct 811 ms 422824 KB Output is correct
32 Correct 1042 ms 275696 KB Output is correct
33 Correct 1586 ms 289432 KB Output is correct
34 Correct 1812 ms 294888 KB Output is correct
35 Correct 1717 ms 292184 KB Output is correct
36 Correct 1817 ms 303344 KB Output is correct
37 Correct 1124 ms 274556 KB Output is correct
38 Execution timed out 2094 ms 438392 KB Time limit exceeded
39 Halted 0 ms 0 KB -