이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<numeric>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define pb push_back
constexpr int INF = 1e9;
int zero_val = INF;
struct Max {
int operator()(const int& a, const int& b) {
return max(a, b);
}
};
struct Min {
int operator()(const int& a, const int& b) {
return min(a, b);
}
};
template<typename T, typename Merge>
struct seg {
Merge merge;
int n;
vector<T> tr;
seg(int n) : merge(Merge()), n(n), tr(2 * n + 1, zero_val) {}
seg(const vector<T>& a) : seg((int)a.size()) {
for (int i = n; i < 2 * n; i++) {
tr[i] = a[i - n];
}
for (int i = n - 1; i >= 1; i--) {
tr[i] = merge(tr[2 * i], tr[2 * i] + 1);
}
}
void upd(int g, const T& k) {
for (tr[g += n] = k; g > 1; g /= 2) {
tr[g / 2] = merge(tr[g], tr[g ^ 1]);
}
}
T query(int l, int r) {
r++;
T res = zero_val;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) res = merge(res, tr[l++]);
if (r & 1) res = merge(res, tr[--r]);
}
return res;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto& u : a) {
cin >> u;
u--;
}
vector c = a;
for (int i = 0; i < n; i++) {
c[a[i]] = i;
}
a = c;
for (auto& u : a) u++;
for (auto& u : b)
cin >> u;
c = b;
sort(all(c));
c.erase(unique(all(c)), c.end());
for (auto& u : b) {
u = lower_bound(all(c), u) - c.begin();
}
c.clear();
vector<int> order(n);
iota(all(order), 0);
sort(all(order), [&](int i, int j) {
return a[i] < a[j];
});
vector<int> a_inv(a);
for (int i = 0; i < n; i++) {
a_inv[a[i]] = i;
}
vector<int> less_under(n), great_under(n);
{
zero_val = -INF;
seg<int, Max> tree(vector<int>(n, -INF));
for (const auto& idx : order) {
less_under[idx] = tree.query(0, idx - 1);
tree.upd(idx, a[idx]);
}
for (int i = 0; i < n; i++) {
if (less_under[i] < 0) {
less_under[i] = -1;
} else {
assert(less_under[i] >= 0 and less_under[i] < n);
less_under[i] = a_inv[less_under[i]];
}
}
}
{
reverse(all(order));
zero_val = INF;
seg<int, Min> tree(vector<int>(n, INF));
for (const auto& idx : order) {
great_under[idx] = tree.query(0, idx - 1);
tree.upd(idx, a[idx]);
}
for (int i = 0; i < n; i++) {
if (great_under[i] >= n) {
great_under[i] = -1;
} else {
assert(great_under[i] >= 0 and great_under[i] < n);
great_under[i] = a_inv[great_under[i]];
}
}
}
#ifdef LOCAL
cout << "A after processing: "; for (auto u : a) cout << u << " "; cout << "\n";
#endif
#ifdef LOCAL
cout << "less under: "; for (auto u : less_under) cout << u << " "; cout << "\n";
cout << "great under: "; for (auto u : great_under) cout << u << " "; cout << "\n";
#endif
order.clear();
auto check_kmp = [&](int end_idx, int j, const vector<int>& a) -> bool {
assert(j >= 1);
int less_under_idx = less_under[j - 1];
if (less_under_idx != -1) {
int less_dist = j - 1 - less_under_idx;
if (a[end_idx] < a[end_idx - less_dist]) {
return false;
}
}
int great_under_idx = great_under[j - 1];
if (great_under_idx != -1) {
int great_dist = j - 1 - great_under_idx;
if (a[end_idx] > a[end_idx - great_dist]) {
return false;
}
}
return true;
};
vector<int> kmp(n);
for (int i = 1; i < n; i++) {
int j = kmp[i - 1];
while (j >= 0) {
//check j + 1
if (check_kmp(i, j + 1, a)) {
kmp[i] = j + 1;
break;
}
j = kmp[j - 1];
}
}
a.clear();
#ifdef LOCAL
cout << "A KMP: ";
for (auto u : kmp) cout << u << " ";
cout << '\n';
#endif
vector<int> kmp_b(m);
vector<int> ans;
int prev_kmp = 0;
for (int i = 0; i < m; i++) {
int j = prev_kmp;
while (j >= 0) {
if (check_kmp(i, j + 1, b)) {
kmp_b[i] = j + 1;
break;
}
j = kmp[j - 1];
}
prev_kmp = kmp_b[i];
if (kmp_b[i] == n) {
ans.pb(i);
}
}
#ifdef LOCAL
cout << "B KMP: ";
for (auto u : kmp_b)
cout << u << " ";
cout << "\n";
#endif
cout << ans.size() << "\n";
for (auto u : ans)
cout << u + 1 - n + 1 << " ";
cout << '\n';
};
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |