Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- using namespace std;
- const int MAXN = 1000000 + 10;
- int n, k, m, l;
- int a[MAXN], x[MAXN], y[MAXN];
- int indInX[MAXN], indInY[MAXN];
- int mostLeft[MAXN], mostRight[MAXN];
- int minSuf[MAXN];
- int left[MAXN], right[MAXN];
- int leftRes[MAXN], rightRes[MAXN];
- int main()
- {
- scanf("%d %d", &n, &k);
- for (int i = 0; i < n; ++i)
- {
- scanf("%d", &a[i]);
- --a[i];
- }
- scanf("%d %d", &m, &l);
- for (int i = 0; i < m; ++i)
- {
- scanf("%d", &x[i]);
- --x[i];
- }
- for (int i = 0; i < l; ++i)
- {
- scanf("%d", &y[i]);
- --y[i];
- }
- for (int i = 0; i < k; ++i)
- indInX[i] = indInY[i] = -1;
- for (int i = 0; i < m; ++i)
- indInX[x[i]] = i;
- for (int i = 0; i < l; ++i)
- indInY[y[i]] = i;
- for (int i = 0; i < k; ++i)
- mostRight[i] = mostLeft[i] = -1;
- for (int i = 0; i < n; ++i)
- {
- int idx = indInX[a[i]];
- left[i] = -1;
- if (idx > 0)
- left[i] = mostRight[x[idx-1]];
- mostRight[a[i]] = i;
- }
- for (int i = n-1; i >= 0; --i)
- {
- int idy = indInY[a[i]];
- right[i] = -1;
- if (idy > 0)
- right[i] = mostLeft[y[idy-1]];
- mostLeft[a[i]] = i;
- }
- minSuf[0] = mostRight[a[0]];
- for (int i = 1; i < n; ++i)
- {
- minSuf[i] = max(minSuf[i-1], mostRight[a[i]]);
- }
- for (int i = 0; i < n; ++i)
- {
- int idx = indInX[a[i]];
- leftRes[i] = -1;
- if (idx == 0)
- {
- leftRes[i] = i;
- }
- else if (idx > 0 && left[i] != -1)
- {
- leftRes[i] = leftRes[left[i]];
- }
- }
- for (int i = n-1; i >= 0; --i)
- {
- int idy = indInY[a[i]];
- rightRes[i] = -1;
- if (idy == 0)
- {
- rightRes[i] = i;
- }
- else if (idy > 0 && right[i] != -1)
- {
- rightRes[i] = rightRes[right[i]];
- }
- }
- vector<int> res;
- for (int i = 0; i < n; ++i)
- {
- if (a[i] == x[m-1])
- {
- int l = leftRes[i];
- int r = rightRes[i];
- if (l > 0 && r != -1 && minSuf[l-1] > r)
- res.push_back(i+1);
- }
- }
- printf("%d\n", res.size());
- for (int i = 0; i < res.size(); ++i)
- printf("%d%c", res[i], " \n"[i+1==res.size()]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement