oj.uz

답안 #433269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433269 2021-06-19T11:27:05 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3, fast-math, 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:51: warning: bad option '-f fast-math' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O3, fast-math, unroll-loops")
      |                                                   ^
Main.cpp:2:51: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:16:52: warning: bad option '-f fast-math' 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 fast-math' 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 fast-math' 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 fast-math' 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 fast-math' 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 292 ms 28904 KB Output is correct
3 Correct 254 ms 24304 KB Output is correct
4 Correct 303 ms 28848 KB Output is correct
5 Correct 285 ms 27352 KB Output is correct
6 Correct 360 ms 31704 KB Output is correct
7 Correct 374 ms 40752 KB Output is correct
8 Correct 394 ms 40696 KB Output is correct
9 Correct 314 ms 30884 KB Output is correct
10 Correct 162 ms 12040 KB Output is correct
11 Correct 324 ms 41172 KB Output is correct
12 Correct 170 ms 18444 KB Output is correct
13 Correct 256 ms 27440 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1122 ms 424828 KB Output is correct
2 Correct 1338 ms 433312 KB Output is correct
3 Correct 1138 ms 425812 KB Output is correct
4 Correct 776 ms 419424 KB Output is correct
5 Correct 745 ms 419248 KB Output is correct
6 Correct 1385 ms 433596 KB Output is correct
7 Correct 1536 ms 435908 KB Output is correct
8 Correct 1299 ms 431156 KB Output is correct
9 Correct 1449 ms 434112 KB Output is correct
10 Correct 1540 ms 437608 KB Output is correct
11 Correct 1201 ms 426080 KB Output is correct
12 Correct 1074 ms 424548 KB Output is correct
13 Correct 1528 ms 439568 KB Output is correct
14 Correct 1436 ms 437172 KB Output is correct
15 Correct 601 ms 416576 KB Output is correct
16 Correct 1157 ms 439576 KB Output is correct
17 Correct 722 ms 423068 KB Output is correct
18 Correct 700 ms 423148 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 292 ms 28904 KB Output is correct
3 Correct 254 ms 24304 KB Output is correct
4 Correct 303 ms 28848 KB Output is correct
5 Correct 285 ms 27352 KB Output is correct
6 Correct 360 ms 31704 KB Output is correct
7 Correct 374 ms 40752 KB Output is correct
8 Correct 394 ms 40696 KB Output is correct
9 Correct 314 ms 30884 KB Output is correct
10 Correct 162 ms 12040 KB Output is correct
11 Correct 324 ms 41172 KB Output is correct
12 Correct 170 ms 18444 KB Output is correct
13 Correct 256 ms 27440 KB Output is correct
14 Correct 1122 ms 424828 KB Output is correct
15 Correct 1338 ms 433312 KB Output is correct
16 Correct 1138 ms 425812 KB Output is correct
17 Correct 776 ms 419424 KB Output is correct
18 Correct 745 ms 419248 KB Output is correct
19 Correct 1385 ms 433596 KB Output is correct
20 Correct 1536 ms 435908 KB Output is correct
21 Correct 1299 ms 431156 KB Output is correct
22 Correct 1449 ms 434112 KB Output is correct
23 Correct 1540 ms 437608 KB Output is correct
24 Correct 1201 ms 426080 KB Output is correct
25 Correct 1074 ms 424548 KB Output is correct
26 Correct 1528 ms 439568 KB Output is correct
27 Correct 1436 ms 437172 KB Output is correct
28 Correct 601 ms 416576 KB Output is correct
29 Correct 1157 ms 439576 KB Output is correct
30 Correct 722 ms 423068 KB Output is correct
31 Correct 700 ms 423148 KB Output is correct
32 Correct 982 ms 275664 KB Output is correct
33 Correct 1407 ms 289440 KB Output is correct
34 Correct 1574 ms 294804 KB Output is correct
35 Correct 1497 ms 292132 KB Output is correct
36 Correct 1516 ms 303348 KB Output is correct
37 Correct 980 ms 274504 KB Output is correct
38 Execution timed out 2105 ms 439340 KB Time limit exceeded
39 Halted 0 ms 0 KB -