Nastya Is Buying Lunch

https://codeforces.com/contest/1136/problem/D

Problem - D - Codeforces

#include<stdio.h>
 
// 중요 포인트
// 1. 주인공이 앞에 있는 사람 a와 교체를 못하면, a는 주인공 앞에 계속 남아있음.
// 2. 주인공과 사람 a와 교체할 수 있다면, a는 영원히 무시해도 됨.
// (증명) 가정 : a를 무시했는데, 주인공이 앞으로 갈 수 있는 기회가 상실됨 -> a가 앞에 있는 b에게 단독으로 영향을 줌 ->
// a가 있어서 b를 주인공 앞으로 데려올 있음. 여기서 주인공과 b는 교체가능하다는 가정이 필요함.
// 이 가정은 b가 a 바로 앞에 있어야하므로 b를 a 바로 앞으로 데려와야하는데 이때 a와 b 사이 다른 모든 vertex와
// 교체가능해야만 가능함. 이 때 a만 b에게 단독으로 영향을 준다는 가정과 모순됨. 따라서 a를 버려도 답에
// 영향이 없음.
// 주인공 앞에 숫자가 있다는 것 -> 다른 요구사항을 요구하므로 버리는 것이 맞다.
// 아래 cnt 배열의 의미 : 주인공과 해당 vertex 사이에 이동하지 못하는 vertex가 있거나 없을 수 있는데,
// 이 vertex 중 교체 가능한 것의 갯수를 의미
// 못가는 것이 총 3개이면 이 3개의 vertex와 교체 가능해야 주인공이 이동이 가능함
 
using namespace std;
const int maxn = 500005;
int p[maxn], cnt[maxn], n, m, x, y, ans;
vector<int> v[maxn];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        v[y].push_back(x);
    }
    for (int i = n; i >= 1; i--) {
        if (cnt[p[i]] == n - i - ans && i != n) ans++;
        else    for (int j = 0; j < v[p[i]].size(); j++) cnt[v[p[i]][j]]++;
    }
    printf("%d", ans);
    return 0;
}