Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n, k; cin >> n >> k;
- vector<int> c(1+n);
- for (int i = 1; i <= n; ++i) cin >> c[i];
- int m, l; cin >> m >> l;
- vector<int> x(1+m), y(1+l);
- for (int i = 1; i <= m; ++i) cin >> x[i];
- for (int i = 1; i <= l; ++i) cin >> y[i];
- vector<int> posInX(1+k);
- for (int i = 1; i <= m; ++i) posInX[x[i]] = i;
- vector<int> closestFinishX(1+n); // rightmost finish to the left of i
- vector<int> lastSeen(1+k);
- for (int i = 1; i <= n; ++i) {
- lastSeen[c[i]] = i;
- if (posInX[c[i]] == 1) closestFinishX[i] = i;
- else if (posInX[c[i]] > 1) closestFinishX[i] = closestFinishX[lastSeen[x[posInX[c[i]]-1]]];
- }
- vector<int> posInY(1+k);
- for (int i = 1; i <= l; ++i) posInY[y[i]] = i;
- vector<int> closestFinishY(1+n+1, n+1); // leftmost finish to the right of i
- lastSeen.assign(1+k, n+1);
- for (int i = n; i > 0; --i) {
- lastSeen[c[i]] = i;
- if (posInY[c[i]] == 1) closestFinishY[i] = i;
- else if (posInY[c[i]] > 1) closestFinishY[i] = closestFinishY[lastSeen[y[posInY[c[i]]-1]]];
- }
- vector<int> first(1+k), last(1+k);
- for (int i = 1; i <= n; ++i) {
- if (!first[c[i]]) first[c[i]] = i;
- last[c[i]] = i;
- }
- vector<pair<int, int>> farthestPairs;
- for (int i = 1; i <= k; ++i) {
- if (first[i] != last[i]) farthestPairs.emplace_back(first[i], last[i]);
- }
- sort(farthestPairs.begin(), farthestPairs.end());
- vector<int> meetingPoints;
- for (int i = 0, nextPair = 0, maxR = 0; i < n; ++i) {
- if (c[i] != x.back()) continue;
- int left = closestFinishX[i], right = closestFinishY[i];
- while (nextPair < (int)farthestPairs.size() && farthestPairs[nextPair].first < left) {
- maxR = max(maxR, farthestPairs[nextPair++].second);
- }
- if (maxR > right) meetingPoints.push_back(i);
- }
- cout << meetingPoints.size() << endl;
- for (int v : meetingPoints) cout << v << ' ';
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement