oj.uz

Submission #433265

# Submission time Handle Problem Language Result Execution time Memory
433265 2021-06-19T11:12:28 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 463608 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(.2), 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 4 ms 4428 KB Output is correct
2 Correct 319 ms 64552 KB Output is correct
3 Correct 248 ms 33588 KB Output is correct
4 Correct 281 ms 37884 KB Output is correct
5 Correct 274 ms 36252 KB Output is correct
6 Correct 341 ms 64524 KB Output is correct
7 Correct 342 ms 64520 KB Output is correct
8 Correct 348 ms 64540 KB Output is correct
9 Correct 321 ms 64412 KB Output is correct
10 Correct 187 ms 18528 KB Output is correct
11 Correct 307 ms 64848 KB Output is correct
12 Correct 204 ms 33852 KB Output is correct
13 Correct 262 ms 36212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1275 ms 429268 KB Output is correct
2 Correct 1452 ms 442056 KB Output is correct
3 Correct 1208 ms 437412 KB Output is correct
4 Correct 913 ms 421568 KB Output is correct
5 Correct 809 ms 421332 KB Output is correct
6 Correct 1373 ms 442264 KB Output is correct
7 Correct 1486 ms 444524 KB Output is correct
8 Correct 1345 ms 439784 KB Output is correct
9 Correct 1401 ms 442872 KB Output is correct
10 Correct 1384 ms 461172 KB Output is correct
11 Correct 1211 ms 437684 KB Output is correct
12 Correct 1204 ms 428932 KB Output is correct
13 Correct 1427 ms 463088 KB Output is correct
14 Correct 1394 ms 446032 KB Output is correct
15 Correct 639 ms 417740 KB Output is correct
16 Correct 1123 ms 463236 KB Output is correct
17 Correct 714 ms 427576 KB Output is correct
18 Correct 771 ms 427220 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 319 ms 64552 KB Output is correct
3 Correct 248 ms 33588 KB Output is correct
4 Correct 281 ms 37884 KB Output is correct
5 Correct 274 ms 36252 KB Output is correct
6 Correct 341 ms 64524 KB Output is correct
7 Correct 342 ms 64520 KB Output is correct
8 Correct 348 ms 64540 KB Output is correct
9 Correct 321 ms 64412 KB Output is correct
10 Correct 187 ms 18528 KB Output is correct
11 Correct 307 ms 64848 KB Output is correct
12 Correct 204 ms 33852 KB Output is correct
13 Correct 262 ms 36212 KB Output is correct
14 Correct 1275 ms 429268 KB Output is correct
15 Correct 1452 ms 442056 KB Output is correct
16 Correct 1208 ms 437412 KB Output is correct
17 Correct 913 ms 421568 KB Output is correct
18 Correct 809 ms 421332 KB Output is correct
19 Correct 1373 ms 442264 KB Output is correct
20 Correct 1486 ms 444524 KB Output is correct
21 Correct 1345 ms 439784 KB Output is correct
22 Correct 1401 ms 442872 KB Output is correct
23 Correct 1384 ms 461172 KB Output is correct
24 Correct 1211 ms 437684 KB Output is correct
25 Correct 1204 ms 428932 KB Output is correct
26 Correct 1427 ms 463088 KB Output is correct
27 Correct 1394 ms 446032 KB Output is correct
28 Correct 639 ms 417740 KB Output is correct
29 Correct 1123 ms 463236 KB Output is correct
30 Correct 714 ms 427576 KB Output is correct
31 Correct 771 ms 427220 KB Output is correct
32 Correct 1063 ms 277724 KB Output is correct
33 Correct 1426 ms 298344 KB Output is correct
34 Correct 1493 ms 318156 KB Output is correct
35 Correct 1442 ms 301020 KB Output is correct
36 Correct 1448 ms 321152 KB Output is correct
37 Correct 1000 ms 277404 KB Output is correct
38 Execution timed out 2116 ms 463608 KB Time limit exceeded
39 Halted 0 ms 0 KB -