oj.uz

Submission #433261

# Submission time Handle Problem Language Result Execution time Memory
433261 2021-06-19T11:07:23 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439500 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, 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:2:74: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math")
      |                                                                          ^
Main.cpp:2:74: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:2:74: warning: bad option '-f fast-math' 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:16:52: warning: bad option '-f fast-math' 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:26:26: warning: bad option '-f fast-math' 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:32:22: warning: bad option '-f fast-math' 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:45:33: warning: bad option '-f fast-math' 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:52:10: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
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 350 ms 28920 KB Output is correct
3 Correct 246 ms 21572 KB Output is correct
4 Correct 353 ms 28792 KB Output is correct
5 Correct 280 ms 24552 KB Output is correct
6 Correct 360 ms 31704 KB Output is correct
7 Correct 425 ms 34228 KB Output is correct
8 Correct 361 ms 33068 KB Output is correct
9 Correct 345 ms 30892 KB Output is correct
10 Correct 170 ms 11900 KB Output is correct
11 Correct 347 ms 32364 KB Output is correct
12 Correct 210 ms 18456 KB Output is correct
13 Correct 252 ms 24684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 423500 KB Output is correct
2 Correct 1717 ms 430392 KB Output is correct
3 Correct 1273 ms 425876 KB Output is correct
4 Correct 867 ms 418820 KB Output is correct
5 Correct 856 ms 418516 KB Output is correct
6 Correct 1623 ms 430572 KB Output is correct
7 Correct 1853 ms 432904 KB Output is correct
8 Correct 1494 ms 428308 KB Output is correct
9 Correct 1707 ms 431340 KB Output is correct
10 Correct 1583 ms 437648 KB Output is correct
11 Correct 1255 ms 426032 KB Output is correct
12 Correct 1275 ms 423116 KB Output is correct
13 Correct 1639 ms 439468 KB Output is correct
14 Correct 1530 ms 437324 KB Output is correct
15 Correct 668 ms 416184 KB Output is correct
16 Correct 1271 ms 439500 KB Output is correct
17 Correct 786 ms 421696 KB Output is correct
18 Correct 764 ms 421536 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 350 ms 28920 KB Output is correct
3 Correct 246 ms 21572 KB Output is correct
4 Correct 353 ms 28792 KB Output is correct
5 Correct 280 ms 24552 KB Output is correct
6 Correct 360 ms 31704 KB Output is correct
7 Correct 425 ms 34228 KB Output is correct
8 Correct 361 ms 33068 KB Output is correct
9 Correct 345 ms 30892 KB Output is correct
10 Correct 170 ms 11900 KB Output is correct
11 Correct 347 ms 32364 KB Output is correct
12 Correct 210 ms 18456 KB Output is correct
13 Correct 252 ms 24684 KB Output is correct
14 Correct 1327 ms 423500 KB Output is correct
15 Correct 1717 ms 430392 KB Output is correct
16 Correct 1273 ms 425876 KB Output is correct
17 Correct 867 ms 418820 KB Output is correct
18 Correct 856 ms 418516 KB Output is correct
19 Correct 1623 ms 430572 KB Output is correct
20 Correct 1853 ms 432904 KB Output is correct
21 Correct 1494 ms 428308 KB Output is correct
22 Correct 1707 ms 431340 KB Output is correct
23 Correct 1583 ms 437648 KB Output is correct
24 Correct 1255 ms 426032 KB Output is correct
25 Correct 1275 ms 423116 KB Output is correct
26 Correct 1639 ms 439468 KB Output is correct
27 Correct 1530 ms 437324 KB Output is correct
28 Correct 668 ms 416184 KB Output is correct
29 Correct 1271 ms 439500 KB Output is correct
30 Correct 786 ms 421696 KB Output is correct
31 Correct 764 ms 421536 KB Output is correct
32 Correct 996 ms 274908 KB Output is correct
33 Correct 1565 ms 286664 KB Output is correct
34 Correct 1668 ms 294636 KB Output is correct
35 Correct 1762 ms 289332 KB Output is correct
36 Correct 1707 ms 297908 KB Output is correct
37 Correct 1061 ms 274588 KB Output is correct
38 Execution timed out 2100 ms 439156 KB Time limit exceeded
39 Halted 0 ms 0 KB -