oj.uz

답안 #433249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433249 2021-06-19T10:56:14 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 439600 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "O3")

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: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 353 ms 28864 KB Output is correct
3 Correct 286 ms 21552 KB Output is correct
4 Correct 348 ms 28812 KB Output is correct
5 Correct 309 ms 24488 KB Output is correct
6 Correct 370 ms 31808 KB Output is correct
7 Correct 406 ms 34208 KB Output is correct
8 Correct 377 ms 32928 KB Output is correct
9 Correct 372 ms 30764 KB Output is correct
10 Correct 168 ms 11912 KB Output is correct
11 Correct 359 ms 32316 KB Output is correct
12 Correct 201 ms 18540 KB Output is correct
13 Correct 268 ms 24596 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1442 ms 423492 KB Output is correct
2 Correct 1665 ms 430424 KB Output is correct
3 Correct 1205 ms 426032 KB Output is correct
4 Correct 839 ms 418772 KB Output is correct
5 Correct 750 ms 418508 KB Output is correct
6 Correct 1723 ms 430680 KB Output is correct
7 Correct 1837 ms 432944 KB Output is correct
8 Correct 1452 ms 428156 KB Output is correct
9 Correct 1692 ms 431248 KB Output is correct
10 Correct 1663 ms 437520 KB Output is correct
11 Correct 1370 ms 426100 KB Output is correct
12 Correct 1317 ms 423112 KB Output is correct
13 Correct 1661 ms 439476 KB Output is correct
14 Correct 1580 ms 437184 KB Output is correct
15 Correct 679 ms 416288 KB Output is correct
16 Correct 1281 ms 439600 KB Output is correct
17 Correct 810 ms 421664 KB Output is correct
18 Correct 779 ms 421488 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 353 ms 28864 KB Output is correct
3 Correct 286 ms 21552 KB Output is correct
4 Correct 348 ms 28812 KB Output is correct
5 Correct 309 ms 24488 KB Output is correct
6 Correct 370 ms 31808 KB Output is correct
7 Correct 406 ms 34208 KB Output is correct
8 Correct 377 ms 32928 KB Output is correct
9 Correct 372 ms 30764 KB Output is correct
10 Correct 168 ms 11912 KB Output is correct
11 Correct 359 ms 32316 KB Output is correct
12 Correct 201 ms 18540 KB Output is correct
13 Correct 268 ms 24596 KB Output is correct
14 Correct 1442 ms 423492 KB Output is correct
15 Correct 1665 ms 430424 KB Output is correct
16 Correct 1205 ms 426032 KB Output is correct
17 Correct 839 ms 418772 KB Output is correct
18 Correct 750 ms 418508 KB Output is correct
19 Correct 1723 ms 430680 KB Output is correct
20 Correct 1837 ms 432944 KB Output is correct
21 Correct 1452 ms 428156 KB Output is correct
22 Correct 1692 ms 431248 KB Output is correct
23 Correct 1663 ms 437520 KB Output is correct
24 Correct 1370 ms 426100 KB Output is correct
25 Correct 1317 ms 423112 KB Output is correct
26 Correct 1661 ms 439476 KB Output is correct
27 Correct 1580 ms 437184 KB Output is correct
28 Correct 679 ms 416288 KB Output is correct
29 Correct 1281 ms 439600 KB Output is correct
30 Correct 810 ms 421664 KB Output is correct
31 Correct 779 ms 421488 KB Output is correct
32 Correct 1006 ms 274900 KB Output is correct
33 Correct 1576 ms 286628 KB Output is correct
34 Correct 1680 ms 294616 KB Output is correct
35 Correct 1775 ms 289412 KB Output is correct
36 Correct 1670 ms 297600 KB Output is correct
37 Correct 995 ms 274680 KB Output is correct
38 Execution timed out 2112 ms 439088 KB Time limit exceeded
39 Halted 0 ms 0 KB -