8705 | 2024-01-25 20:32:01 | mraron | Túlcsordulás | cpp17 | Accepted 100/100 | 219ms | 24256 KiB |
// @check-accepted: examples quadratic X=Y no-limits
#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#define int long long
using namespace std;
int N;
string A, B;
constexpr int mod = 1e9 + 7;
constexpr int base1 = 2;
constexpr int base2 = 7;
vector<int> p1;
vector<int> p2;
struct Hash {
vector<int> h1;
vector<int> h2;
Hash(const string& s) {
int n = s.size();
h1.resize(n + 1);
h2.resize(n + 1);
for (int i = 0; i < n; ++i) {
h1[i + 1] = (h1[i] * base1 + s[i] - '0') % mod;
h2[i + 1] = (h2[i] * base2 + s[i] - '0') % mod;
}
}
pair<int, int> get(int l, int r) {
return {(h1[r + 1] - h1[l] * p1[r - l + 1] % mod + mod) % mod, (h2[r + 1] - h2[l] * p2[r - l + 1] % mod + mod) % mod};
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
p1.resize(N + 1);
p1[0] = 1;
for (int i = 1; i <= N; ++i) {
p1[i] = p1[i - 1] * base1 % mod;
}
p2.resize(N + 1);
p2[0] = 1;
for (int i = 1; i <= N; ++i) {
p2[i] = p2[i - 1] * base2 % mod;
}
cin >> A;
cin >> B;
for (int i = 0; i < N; ++i) {
B[i] = 1 - (B[i] - '0') + '0';
}
Hash ha(A), hb(B);
int Q;
cin >> Q;
for (int i = 0; i < Q; ++i) {
int X, Y, L;
cin >> X >> Y >> L;
int l = 0, r = L;
while (l < r) {
int m = (l + r) / 2;
if (ha.get(X, X + m) == hb.get(Y, Y + m)) {
l = m + 1;
} else {
r = m;
}
}
if (l == L) {
cout << 1 << " ";
} else {
cout << B[Y + l] << " ";
}
}
cout << '\n';
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1828 KiB | ||||
2 | Accepted | 3ms | 2020 KiB | ||||
subtask2 | 40/40 | ||||||
3 | Accepted | 3ms | 2104 KiB | ||||
4 | Accepted | 3ms | 2232 KiB | ||||
5 | Accepted | 4ms | 2472 KiB | ||||
6 | Accepted | 3ms | 3088 KiB | ||||
7 | Accepted | 3ms | 3048 KiB | ||||
8 | Accepted | 4ms | 3048 KiB | ||||
9 | Accepted | 4ms | 3296 KiB | ||||
subtask3 | 30/30 | ||||||
10 | Accepted | 3ms | 3080 KiB | ||||
11 | Accepted | 17ms | 4156 KiB | ||||
12 | Accepted | 79ms | 11464 KiB | ||||
13 | Accepted | 59ms | 15468 KiB | ||||
14 | Accepted | 149ms | 23284 KiB | ||||
15 | Accepted | 145ms | 22224 KiB | ||||
16 | Accepted | 143ms | 21480 KiB | ||||
17 | Accepted | 202ms | 23312 KiB | ||||
subtask4 | 30/30 | ||||||
18 | Accepted | 8ms | 4616 KiB | ||||
19 | Accepted | 37ms | 23500 KiB | ||||
20 | Accepted | 56ms | 8676 KiB | ||||
21 | Accepted | 86ms | 18412 KiB | ||||
22 | Accepted | 219ms | 23756 KiB | ||||
23 | Accepted | 216ms | 24040 KiB | ||||
24 | Accepted | 143ms | 22940 KiB | ||||
25 | Accepted | 211ms | 22112 KiB | ||||
26 | Accepted | 212ms | 24160 KiB | ||||
27 | Accepted | 145ms | 24244 KiB | ||||
28 | Accepted | 216ms | 24256 KiB |