oj.uz

답안 #433262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
433262 2021-06-19T11:09:55 Z parsabahrami Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 481376 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() {
  	mp.max_load_factor(.13), 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: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: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 273 ms 46948 KB Output is correct
3 Correct 276 ms 46968 KB Output is correct
4 Correct 293 ms 46920 KB Output is correct
5 Correct 322 ms 46952 KB Output is correct
6 Correct 372 ms 91420 KB Output is correct
7 Correct 365 ms 91428 KB Output is correct
8 Correct 375 ms 91416 KB Output is correct
9 Correct 335 ms 91428 KB Output is correct
10 Correct 222 ms 25016 KB Output is correct
11 Correct 324 ms 91824 KB Output is correct
12 Correct 227 ms 47076 KB Output is correct
13 Correct 251 ms 47356 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1230 ms 433404 KB Output is correct
2 Correct 1381 ms 450684 KB Output is correct
3 Correct 1195 ms 434552 KB Output is correct
4 Correct 976 ms 423676 KB Output is correct
5 Correct 936 ms 423464 KB Output is correct
6 Correct 1388 ms 450824 KB Output is correct
7 Correct 1438 ms 453256 KB Output is correct
8 Correct 1389 ms 448464 KB Output is correct
9 Correct 1374 ms 451540 KB Output is correct
10 Correct 1367 ms 454996 KB Output is correct
11 Correct 1247 ms 446364 KB Output is correct
12 Correct 1181 ms 433244 KB Output is correct
13 Correct 1459 ms 480756 KB Output is correct
14 Correct 1349 ms 454700 KB Output is correct
15 Correct 755 ms 418612 KB Output is correct
16 Correct 1116 ms 480848 KB Output is correct
17 Correct 742 ms 431728 KB Output is correct
18 Correct 750 ms 431540 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 273 ms 46948 KB Output is correct
3 Correct 276 ms 46968 KB Output is correct
4 Correct 293 ms 46920 KB Output is correct
5 Correct 322 ms 46952 KB Output is correct
6 Correct 372 ms 91420 KB Output is correct
7 Correct 365 ms 91428 KB Output is correct
8 Correct 375 ms 91416 KB Output is correct
9 Correct 335 ms 91428 KB Output is correct
10 Correct 222 ms 25016 KB Output is correct
11 Correct 324 ms 91824 KB Output is correct
12 Correct 227 ms 47076 KB Output is correct
13 Correct 251 ms 47356 KB Output is correct
14 Correct 1230 ms 433404 KB Output is correct
15 Correct 1381 ms 450684 KB Output is correct
16 Correct 1195 ms 434552 KB Output is correct
17 Correct 976 ms 423676 KB Output is correct
18 Correct 936 ms 423464 KB Output is correct
19 Correct 1388 ms 450824 KB Output is correct
20 Correct 1438 ms 453256 KB Output is correct
21 Correct 1389 ms 448464 KB Output is correct
22 Correct 1374 ms 451540 KB Output is correct
23 Correct 1367 ms 454996 KB Output is correct
24 Correct 1247 ms 446364 KB Output is correct
25 Correct 1181 ms 433244 KB Output is correct
26 Correct 1459 ms 480756 KB Output is correct
27 Correct 1349 ms 454700 KB Output is correct
28 Correct 755 ms 418612 KB Output is correct
29 Correct 1116 ms 480848 KB Output is correct
30 Correct 742 ms 431728 KB Output is correct
31 Correct 750 ms 431540 KB Output is correct
32 Correct 1160 ms 279924 KB Output is correct
33 Correct 1490 ms 306908 KB Output is correct
34 Correct 1561 ms 312056 KB Output is correct
35 Correct 1441 ms 309596 KB Output is correct
36 Correct 1458 ms 338700 KB Output is correct
37 Correct 1125 ms 279748 KB Output is correct
38 Execution timed out 2094 ms 481376 KB Time limit exceeded
39 Halted 0 ms 0 KB -