제출 #830843

#제출 시각아이디문제언어결과실행 시간메모리
830843trytovoiMatching (CEOI11_mat)C++14
0 / 100
943 ms27628 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() const int MX = (int) 1e6 + 5; const int mod = (int) 1e9 + 7; const int BASE = MX + 2; void add(int& x, int y) { if ((x += y) >= mod) x -= mod; } int sadd(int x, int y) { add(x, y); return x; } void sub(int& x, int y) { if ((x -= y) < 0) x += mod; } int ssub(int x, int y) { sub(x, y); return x; } int n, m; int a[MX], b[MX], c[MX]; int pw[MX], prefix[MX]; class segtree { public: struct node { int val = 0; int cnt = 0; void apply(int l, int r, int v) { if (v == -1) val = cnt = 0; else { val = v; cnt = 1; } } }; node unite(const node &a, const node &b) const { node res; res.cnt = a.cnt + b.cnt; res.val = sadd(a.val, (1LL * pw[a.cnt] * b.val % mod)); return res; } inline void push(int x, int l, int r) { } inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); } int n; vector<node> tree; void build(int x, int l, int r) { if (l == r) { return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); build(x + 1, l, y); build(z, y + 1, r); pull(x, z); } template <typename M> void build(int x, int l, int r, const vector<M> &v) { if (l == r) { tree[x].apply(l, r, v[l]); return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); build(x + 1, l, y, v); build(z, y + 1, r, v); pull(x, z); } node get(int x, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return tree[x]; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); push(x, l, r); node res{}; if (rr <= y) { res = get(x + 1, l, y, ll, rr); } else { if (ll > y) { res = get(z, y + 1, r, ll, rr); } else { res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr)); } } pull(x, z); return res; } template <typename... M> void modify(int x, int l, int r, int ll, int rr, const M&... v) { if (ll <= l && r <= rr) { tree[x].apply(l, r, v...); return; } int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); push(x, l, r); if (ll <= y) { modify(x + 1, l, y, ll, rr, v...); } if (rr > y) { modify(z, y + 1, r, ll, rr, v...); } pull(x, z); } int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) { if (l == r) { return l; } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res; if (f(tree[x + 1])) { res = find_first_knowingly(x + 1, l, y, f); } else { res = find_first_knowingly(z, y + 1, r, f); } pull(x, z); return res; } int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) { if (ll <= l && r <= rr) { if (!f(tree[x])) { return -1; } return find_first_knowingly(x, l, r, f); } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res = -1; if (ll <= y) { res = find_first(x + 1, l, y, ll, rr, f); } if (rr > y && res == -1) { res = find_first(z, y + 1, r, ll, rr, f); } pull(x, z); return res; } int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) { if (l == r) { return l; } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res; if (f(tree[z])) { res = find_last_knowingly(z, y + 1, r, f); } else { res = find_last_knowingly(x + 1, l, y, f); } pull(x, z); return res; } int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) { if (ll <= l && r <= rr) { if (!f(tree[x])) { return -1; } return find_last_knowingly(x, l, r, f); } push(x, l, r); int y = (l + r) >> 1; int z = x + ((y - l + 1) << 1); int res = -1; if (rr > y) { res = find_last(z, y + 1, r, ll, rr, f); } if (ll <= y && res == -1) { res = find_last(x + 1, l, y, ll, rr, f); } pull(x, z); return res; } segtree(int _n) : n(_n) { assert(n > 0); tree.resize(2 * n - 1); build(0, 0, n - 1); } template <typename M> segtree(const vector<M> &v) { n = v.size(); assert(n > 0); tree.resize(2 * n - 1); build(0, 0, n - 1, v); } node get(int ll, int rr) { assert(0 <= ll && ll <= rr && rr <= n - 1); return get(0, 0, n - 1, ll, rr); } node get(int p) { assert(0 <= p && p <= n - 1); return get(0, 0, n - 1, p, p); } template <typename... M> void modify(int ll, int rr, const M&... v) { assert(0 <= ll && ll <= rr && rr <= n - 1); modify(0, 0, n - 1, ll, rr, v...); } // find_first and find_last call all FALSE elements // to the left (right) of the sought position exactly once int find_first(int ll, int rr, const function<bool(const node&)> &f) { assert(0 <= ll && ll <= rr && rr <= n - 1); return find_first(0, 0, n - 1, ll, rr, f); } int find_last(int ll, int rr, const function<bool(const node&)> &f) { assert(0 <= ll && ll <= rr && rr <= n - 1); return find_last(0, 0, n - 1, ll, rr, f); } }; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; pw[0] = 1; prefix[0] = 1; for (int i = 1; i <= n; ++i) { pw[i] = 1LL * pw[i - 1] * BASE % mod; prefix[i] = sadd(prefix[i - 1], pw[i]); } int hashA = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; c[a[i]] = i; } for (int i = 1; i <= n; ++i) add(hashA, 1LL * pw[i - 1] * c[i] % mod); vector<int> vec; for (int i = 1; i <= m; ++i) { cin >> b[i]; vec.push_back(b[i]); } sort(all(vec)); vec.resize(unique(all(vec)) - vec.begin()); for (int i = 1; i <= m; ++i) b[i] = lower_bound(all(vec), b[i]) - vec.begin() + 1; segtree st(m + 1); for (int i = 1; i <= n; ++i) { int ind = b[i], val = i; st.modify<int>(ind, ind, val); } vector<int> ans; if (st.get(1, m).val == hashA) ans.push_back(1); for (int i = 2; i <= m - n + 1; ++i) { int ind = b[i - 1], val = -1; st.modify<int>(ind, ind, val); ind = b[i + n - 1], val = i + n - 1; st.modify<int>(ind, ind, val); add(hashA, prefix[n - 1]); if (hashA == st.get(1, m).val) ans.push_back(i); } cout << (int) ans.size() << '\n'; for (int x : ans) cout << x << ' '; return 0; } /** 6 12 2 5 3 4 1 6 10 45 25 30 5 47 31 35 4 50 33 20 5 1 3 4 2 6 BASE^0 * 5 + BASE^1 * 1 + BASE^2 * 3 + BASE^3 * 4 + BASE^4 * 2 + BASE^5 * 6 10 45 25 30 5 47 => 5 1 3 4 2 6 5 6 7 8 9 10 5 47 31 35 4 50 => 9 5 7 8 6 10 BASE^0 * 9 + BASE^1 * 5 + BASE^2 * 7 + BASE^3 * 8 + BASE^4 * 6 + BASE^5 * 10 4 6 1 3 4 2 29 43 2 23 43 9 1 4 2 3 1 * BASE^0 + 4 * BASE^1 + 2 * BASE^2 + 3 * BASE^3 3 4 5 6 2 23 43 9 => 3 6 4 5 3 * BASE^0 + 6 * BASE^1 + 4 * BASE^2 + 5 * BASE^3 **/
#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...