제출 #836718

#제출 시각아이디문제언어결과실행 시간메모리
836718ToniBMatching (CEOI11_mat)C++17
0 / 100
2079 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 2; const int OFF = 1 << 21; int n, m, tour[OFF]; int st[OFF][2]; vector<int> a, b, L, R, L_cur, R_cur, ans; void con(int x, int l, int r, vector<int>& vals){ if(l == r){ tour[x] = l; return ; } int mid = (l + r) >> 1; con(x * 2 + 1, l, mid, vals); con(x * 2 + 2, mid + 1, r, vals); if(vals[tour[x * 2 + 1]] > vals[tour[x * 2 + 2]]) tour[x] = tour[x * 2 + 1]; else tour[x] = tour[x * 2 + 2]; } int f(int x, int l, int r, int ql, int qr, vector<int>& vals){ if(ql > r || l > qr) return -1; if(ql <= l && r <= qr) return tour[x]; int mid = (l + r) >> 1; int lval = f(x * 2 + 1, l, mid, ql, qr, vals), rval = f(x * 2 + 2, mid + 1, r, ql, qr, vals); if(lval == -1) return rval; if(rval == -1) return lval; if(vals[lval] > vals[rval]) return lval; return rval; } void make_tree(int l, int r, int node, vector<int>& a, vector<int>& L, vector<int>& R){ if(l != node){ L[node] = f(0, 0, (int)a.size() - 1, l, node - 1, a); make_tree(l, node - 1, L[node], a, L, R); L[node] = node - L[node]; } if(r != node){ R[node] = f(0, 0, (int)a.size() - 1, node + 1, r, a); make_tree(node + 1, r, R[node], a, L, R); R[node] = R[node] - node; } } void prepare(vector<int>& a, vector<int>& L, vector<int>& R){ con(0, 0, (int)a.size() - 1, a); make_tree(0, (int)a.size() - 1, tour[0], a, L, R); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; a.resize(n); b.resize(m); vector<int> inv (n); for(int i = 0; i < n; ++i){ cin >> a[i], --a[i]; inv[a[i]] = i; } swap(a, inv); vector<int> cmp; unordered_map<int, int> um; for(int i = 0; i < m; ++i){ cin >> b[i]; cmp.push_back(b[i]); } sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); for(int i = 0; i < (int)cmp.size(); ++i) um[cmp[i]] = i; for(int i = 0; i < m; ++i) b[i] = um[b[i]]; L.resize(n); R.resize(n); L_cur.resize(m); R_cur.resize(m); prepare(a, L, R); vector<int> pre (n); for(int i = 0; i < n; ++i) pre[i] = b[i]; prepare(pre, L_cur, R_cur); con(0, 0, m - 1, b); bool ok = 1; for(int i = 0; i < n; ++i){ ok &= L[i] == L_cur[i]; ok &= R[i] == R_cur[i]; } if(ok) ans.push_back(0); for(int i = n; i < m; ++i){ // int idx_R = f_st(0, 0, m - 1, b[i], m - 1, 1), idx_L = f_st(0, 0, m - 1, b[i - n], m - 1, 0); int idx_L = m + 1, idx_R = -1; for(int k = i - n + 1; k <= i; ++k){ if(b[k] > b[i - n]){ idx_L = k; break; } } for(int k = i; k >= i - n + 1; --k){ if(b[k] > b[i]){ idx_R = k; break; } } // idx_R = rightmost bigger than b[i], idx_L = leftmost bigger than b[i - n] if(idx_L != m + 1){ assert(L_cur[idx_L] == idx_L - i + n); if(R_cur[i - n] == 0){ L_cur[idx_L] = 0; } else L_cur[idx_L] -= R_cur[i - n]; } if(idx_R == -1){ // b[i] is new maximum int x = f(0, 0, m - 1, i - n + 1, i - 1, b); assert(b[i] > b[x]); L_cur[i] = i - x; } else { if(R_cur[idx_R] == 0) L_cur[i] = 0; else L_cur[i] = i - idx_R - R_cur[idx_R]; R_cur[idx_R] = i - idx_R; } bool ok = 1; int p = 0; for(int j = i - n + 1; j <= i; ++j){ ok &= L_cur[j] == L[p]; ok &= R_cur[j] == R[p++]; } if(ok) ans.push_back(i - n + 1); } cout << ans.size() << "\n"; for(int x : ans) cout << x + 1 << " "; cout << "\n"; return 0; }
#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...