oj.uz

Submission #433267

# Submission time Handle Problem Language Result Execution time Memory
433267 2021-06-19T11:19:59 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 448704 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3, 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(.4), 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:60: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O3, no-stack-protector, unroll-loops")
      |                                                            ^
Main.cpp:2:60: 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 298 ms 42184 KB Output is correct
3 Correct 231 ms 25828 KB Output is correct
4 Correct 351 ms 42072 KB Output is correct
5 Correct 256 ms 28916 KB Output is correct
6 Correct 333 ms 42140 KB Output is correct
7 Correct 331 ms 43032 KB Output is correct
8 Correct 338 ms 42172 KB Output is correct
9 Correct 321 ms 42184 KB Output is correct
10 Correct 201 ms 14104 KB Output is correct
11 Correct 314 ms 42592 KB Output is correct
12 Correct 206 ms 22928 KB Output is correct
13 Correct 237 ms 28960 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 425632 KB Output is correct
2 Correct 1273 ms 434736 KB Output is correct
3 Correct 1069 ms 430192 KB Output is correct
4 Correct 842 ms 420140 KB Output is correct
5 Correct 837 ms 419620 KB Output is correct
6 Correct 1262 ms 434908 KB Output is correct
7 Correct 1402 ms 437300 KB Output is correct
8 Correct 1274 ms 432528 KB Output is correct
9 Correct 1308 ms 435788 KB Output is correct
10 Correct 1329 ms 446328 KB Output is correct
11 Correct 1147 ms 430500 KB Output is correct
12 Correct 1119 ms 425148 KB Output is correct
13 Correct 1283 ms 448196 KB Output is correct
14 Correct 1245 ms 446084 KB Output is correct
15 Correct 598 ms 416808 KB Output is correct
16 Correct 1112 ms 448308 KB Output is correct
17 Correct 780 ms 423852 KB Output is correct
18 Correct 686 ms 423576 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 298 ms 42184 KB Output is correct
3 Correct 231 ms 25828 KB Output is correct
4 Correct 351 ms 42072 KB Output is correct
5 Correct 256 ms 28916 KB Output is correct
6 Correct 333 ms 42140 KB Output is correct
7 Correct 331 ms 43032 KB Output is correct
8 Correct 338 ms 42172 KB Output is correct
9 Correct 321 ms 42184 KB Output is correct
10 Correct 201 ms 14104 KB Output is correct
11 Correct 314 ms 42592 KB Output is correct
12 Correct 206 ms 22928 KB Output is correct
13 Correct 237 ms 28960 KB Output is correct
14 Correct 1123 ms 425632 KB Output is correct
15 Correct 1273 ms 434736 KB Output is correct
16 Correct 1069 ms 430192 KB Output is correct
17 Correct 842 ms 420140 KB Output is correct
18 Correct 837 ms 419620 KB Output is correct
19 Correct 1262 ms 434908 KB Output is correct
20 Correct 1402 ms 437300 KB Output is correct
21 Correct 1274 ms 432528 KB Output is correct
22 Correct 1308 ms 435788 KB Output is correct
23 Correct 1329 ms 446328 KB Output is correct
24 Correct 1147 ms 430500 KB Output is correct
25 Correct 1119 ms 425148 KB Output is correct
26 Correct 1283 ms 448196 KB Output is correct
27 Correct 1245 ms 446084 KB Output is correct
28 Correct 598 ms 416808 KB Output is correct
29 Correct 1112 ms 448308 KB Output is correct
30 Correct 780 ms 423852 KB Output is correct
31 Correct 686 ms 423576 KB Output is correct
32 Correct 1016 ms 276104 KB Output is correct
33 Correct 1386 ms 290928 KB Output is correct
34 Correct 1455 ms 303516 KB Output is correct
35 Correct 1428 ms 293736 KB Output is correct
36 Correct 1485 ms 306408 KB Output is correct
37 Correct 1006 ms 275608 KB Output is correct
38 Execution timed out 2107 ms 448704 KB Time limit exceeded
39 Halted 0 ms 0 KB -