oj.uz

답안 #433266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433266 2021-06-19T11:14:29 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 463848 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(.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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 281 ms 64592 KB Output is correct
3 Correct 226 ms 33596 KB Output is correct
4 Correct 277 ms 37812 KB Output is correct
5 Correct 252 ms 36124 KB Output is correct
6 Correct 366 ms 64484 KB Output is correct
7 Correct 321 ms 64420 KB Output is correct
8 Correct 341 ms 64484 KB Output is correct
9 Correct 306 ms 64496 KB Output is correct
10 Correct 167 ms 18484 KB Output is correct
11 Correct 297 ms 64924 KB Output is correct
12 Correct 190 ms 33848 KB Output is correct
13 Correct 237 ms 36248 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 972 ms 429220 KB Output is correct
2 Correct 1152 ms 442160 KB Output is correct
3 Correct 933 ms 437512 KB Output is correct
4 Correct 803 ms 421692 KB Output is correct
5 Correct 742 ms 421376 KB Output is correct
6 Correct 1115 ms 442180 KB Output is correct
7 Correct 1184 ms 444588 KB Output is correct
8 Correct 1100 ms 439692 KB Output is correct
9 Correct 1115 ms 442956 KB Output is correct
10 Correct 1130 ms 461172 KB Output is correct
11 Correct 1039 ms 437680 KB Output is correct
12 Correct 984 ms 428852 KB Output is correct
13 Correct 1181 ms 463120 KB Output is correct
14 Correct 1184 ms 445980 KB Output is correct
15 Correct 600 ms 417604 KB Output is correct
16 Correct 1029 ms 463272 KB Output is correct
17 Correct 679 ms 427556 KB Output is correct
18 Correct 662 ms 427188 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 281 ms 64592 KB Output is correct
3 Correct 226 ms 33596 KB Output is correct
4 Correct 277 ms 37812 KB Output is correct
5 Correct 252 ms 36124 KB Output is correct
6 Correct 366 ms 64484 KB Output is correct
7 Correct 321 ms 64420 KB Output is correct
8 Correct 341 ms 64484 KB Output is correct
9 Correct 306 ms 64496 KB Output is correct
10 Correct 167 ms 18484 KB Output is correct
11 Correct 297 ms 64924 KB Output is correct
12 Correct 190 ms 33848 KB Output is correct
13 Correct 237 ms 36248 KB Output is correct
14 Correct 972 ms 429220 KB Output is correct
15 Correct 1152 ms 442160 KB Output is correct
16 Correct 933 ms 437512 KB Output is correct
17 Correct 803 ms 421692 KB Output is correct
18 Correct 742 ms 421376 KB Output is correct
19 Correct 1115 ms 442180 KB Output is correct
20 Correct 1184 ms 444588 KB Output is correct
21 Correct 1100 ms 439692 KB Output is correct
22 Correct 1115 ms 442956 KB Output is correct
23 Correct 1130 ms 461172 KB Output is correct
24 Correct 1039 ms 437680 KB Output is correct
25 Correct 984 ms 428852 KB Output is correct
26 Correct 1181 ms 463120 KB Output is correct
27 Correct 1184 ms 445980 KB Output is correct
28 Correct 600 ms 417604 KB Output is correct
29 Correct 1029 ms 463272 KB Output is correct
30 Correct 679 ms 427556 KB Output is correct
31 Correct 662 ms 427188 KB Output is correct
32 Correct 1045 ms 277796 KB Output is correct
33 Correct 1364 ms 298180 KB Output is correct
34 Correct 1341 ms 318292 KB Output is correct
35 Correct 1320 ms 300916 KB Output is correct
36 Correct 1299 ms 321232 KB Output is correct
37 Correct 1052 ms 277464 KB Output is correct
38 Execution timed out 2104 ms 463848 KB Time limit exceeded
39 Halted 0 ms 0 KB -