Submission #433208

#TimeUsernameProblemLanguageResultExecution timeMemory
433208parsabahramiDabbeh (INOI20_dabbeh)C++17
0 / 100
2082 ms184288 KiB
#include <bits/stdc++.h> 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 = 1e9 + 7; int pw[N], H[N], dp[19][N], rmq[19][19][N], lg[N], n, m, q, base = 31; map<int, int> mp; char S[N * 2]; int get_hash(int l, int r) { return (H[r] - 1ll * H[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD; } 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) { assert(l < r); int x = lg[r - l]; return max(rmq[id][x][l], rmq[id][x][r - (1 << x)]); } int get_pos(int l, int x) { if (dp[0][l] < 0) return -1; int p = -1; for (; x; x -= x & -x) { int b = __builtin_ctz(x); assert((1 << b) == (x & -x)); if (!~p) p = dp[b][l]; else p = get_max(b, l, min(p + 2, n + 1)); if (p < 0) return -1; } return p; } int main() { for (int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1; pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = 1ll * pw[i - 1] * base % MOD; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%s", S); int h = 0; for (int j = 0; S[j]; j++) { h = (1ll * h * base % MOD + S[j] - 'a' + 1) % MOD; mp[h] = 1; } } scanf("%s", S + 1); m = strlen(S + 1); for (int i = 1; i <= m; i++) { H[i] = (1ll * H[i - 1] * base % MOD + S[i] - 'a' + 1) % MOD; } 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 >= i ? l : -MOD); } for (int j = 1; j < 19; j++) { build_rmq(j - 1); for (int i = 1; i <= n; i++) { int p = dp[j - 1][i]; if (p > 0) dp[j][i] = get_max(j - 1, i, min(n + 1, p + 2)); else dp[j][i] = -MOD; } } for (; q; q--) { int l, r; scanf("%d%d", &l, &r); l++; int ret = (1 << 19) - 1; for (int i = 18; ~i; i--) { if (get_pos(l, ret ^ (1 << i)) >= r) ret ^= (1 << i); } printf("%d\n", ret != (1 << 19) - 1 ? ret : -1); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%s", S);
      |         ~~~~~^~~~~~~~~
Main.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%s", S + 1); m = strlen(S + 1);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp:89:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         int l, r; scanf("%d%d", &l, &r); l++;
      |                   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...