제출 #830383

#제출 시각아이디문제언어결과실행 시간메모리
830383winthemcut3Matching (CEOI11_mat)C++14
100 / 100
509 ms55876 KiB
#include <bits/stdc++.h> #define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ll long long #define PB push_back #define ALL(v) (v).begin(), (v).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define fi first #define se second #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; /** END OF TEMPLATE **/ const int mxN = 1e6 + 7; struct DSU { vector<int> e, p; DSU(int t) : e(t+1, -1) { p.resize(t+1); FOR(i, 0, t) p[i] = i; } int rep(int u) { return e[u] < 0 ? u : e[u] = rep(e[u]); } int get(int u) { return p[rep(u)]; } void unite(int u, int v, bool st) { u = rep(u); v = rep(v); if(u == v) return; if(e[u] > e[v]) swap(u, v); e[u] += e[v]; e[v] = u; if(st) p[u] = max(p[u], p[v]); else p[u] = min(p[u], p[v]); } }; int l[mxN], r[mxN], pos[mxN]; int n, m; int a[mxN], b[mxN], pi[mxN]; bool check(int st, int i, int j) { if(!st) { //cerr << i << ' ' << j << ' ' << a[i] << ' ' << a[i-r[j]] << '\n'; if(l[j] && i > l[j] && a[i - l[j]] > a[i]) return false; if(r[j] && i > r[j] && a[i - r[j]] < a[i]) return false; //cerr << '*'; return true; } else { if(j == n+1) return false; if(l[j] && i > l[j] && b[i - l[j]] > b[i]) return false; if(r[j] && i > r[j] && b[i - r[j]] < b[i]) return false; return true; } } void calc() { DSU L(n+2), R(n+2); pos[0] = 0, pos[n+1] = n+1; FORD(i, n, 1) { int u = a[i]; int t1 = pos[L.get(u-1)], t2 = pos[R.get(u+1)]; if(t1) l[i] = i - t1; if(t2 < n+1) r[i] = i - t2; L.unite(u, u-1, 0); R.unite(u, u+1, 1); } // cerr << "\nL: "; // FOR(i, 1, n) cout << l[i] << ' '; // cerr << "\nR: "; // FOR(i, 1, n) cout << r[i] << ' '; // cerr << '\n'; } int main() { FastIO; //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); cin >> n >> m; FOR(i, 1, n) { cin >> pos[i]; a[pos[i]] = i; } vector<int> t; FOR(i, 1, m) cin >> b[i], t.PB(b[i]); sort(ALL(t)); FOR(i, 1, m) b[i] = lower_bound(ALL(t), b[i]) - t.begin() + 1; calc(); FOR(i, 2, n) { int j = pi[i-1]; while(j > 0 && !check(0, i, j+1)) j = pi[j]; if(check(0, i, j+1)) j++; pi[i] = j; } int j = 0; vector<int> res; FOR(i, 1, m) { while(j > 0 && !check(1, i, j+1)) j = pi[j]; if(check(1, i, j+1)) j++; if(j == n) res.PB(i - n + 1); } cout << res.size() << '\n'; for(auto &x : res) cout << x << ' '; 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...