Submission #3784729

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;

#define REP(i,n) for (ll i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long ll;

int main ()
{
    int N,M; cin >> N >> M;
    vector < int > A(N);
    REP(i,N) cin >> A[i];

    map < int, int > cnt;
    vector < int > acc(N,0);
    int dup = 0;
    REP(i,N) {
        cnt[A[i]]++;
        int idx = A[i] - cnt[A[i]];
        if (idx < 0) idx = 0;
        if (acc[idx] > 0) dup++;
        acc[idx]++;
    }

    vector < int > ans;
    REP(i,M) {
        
        int X,Y; 
        cin >> X >> Y;
        
        int At = A[X - 1];
        int idx_f = At - cnt[At];
        if (idx_f < 0) idx_f = 0;
        if (acc[idx_f] > 1) dup--;
        acc[idx_f]--;
        cnt[At]--;
        
        cnt[Y]++;
        int idx_t = Y - cnt[Y];
        if (idx_t < 0) idx_t = 0;
        if (acc[idx_t] > 0) dup++;
        acc[idx_t]++;
        ans.push_back(dup);
        A[X - 1] = Y;
    }

    REP(i,ans.size()) cout << ans[i] << endl;

    return 0;
}

Submission Info

Judge Result