제출 #712138

#제출 시각아이디문제언어결과실행 시간메모리
712138badontMatching (CEOI11_mat)C++17
100 / 100
1217 ms51064 KiB
#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 : 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...