Submission #3784719


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 (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

Submission Time
Task C - Snuke and Spells
User kosakkun
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1443 Byte
Status RE
Exec Time 866 ms
Memory 13304 KB

Judge Result

Set Name Sample subtask All
Score / Max Score 0 / 0 0 / 500 0 / 500
Status
AC × 2
RE × 1
AC × 19
RE × 4
AC × 36
RE × 10
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
subtask sample1.txt, sample2.txt, sample3.txt, subtask_a1.txt, subtask_a2.txt, subtask_a3.txt, subtask_a4.txt, subtask_a5.txt, subtask_a6.txt, subtask_b1.txt, subtask_b2.txt, subtask_c1.txt, subtask_c2.txt, subtask_d1.txt, subtask_d2.txt, subtask_d3.txt, subtask_d4.txt, subtask_e1.txt, subtask_e2.txt, subtask_e3.txt, subtask_e4.txt, subtask_f1.txt, subtask_f2.txt
All sample1.txt, sample2.txt, sample3.txt, a1.txt, a2.txt, a3.txt, a4.txt, a5.txt, a6.txt, b1.txt, b2.txt, c1.txt, c2.txt, d1.txt, d2.txt, d3.txt, d4.txt, e1.txt, e2.txt, e3.txt, e4.txt, f1.txt, f2.txt, sample1.txt, sample2.txt, sample3.txt, subtask_a1.txt, subtask_a2.txt, subtask_a3.txt, subtask_a4.txt, subtask_a5.txt, subtask_a6.txt, subtask_b1.txt, subtask_b2.txt, subtask_c1.txt, subtask_c2.txt, subtask_d1.txt, subtask_d2.txt, subtask_d3.txt, subtask_d4.txt, subtask_e1.txt, subtask_e2.txt, subtask_e3.txt, subtask_e4.txt, subtask_f1.txt, subtask_f2.txt
Case Name Status Exec Time Memory
a1.txt AC 743 ms 11892 KB
a2.txt AC 753 ms 11892 KB
a3.txt RE 866 ms 11764 KB
a4.txt AC 752 ms 11764 KB
a5.txt RE 845 ms 11380 KB
a6.txt AC 769 ms 11892 KB
b1.txt AC 787 ms 13304 KB
b2.txt AC 786 ms 13304 KB
c1.txt RE 825 ms 13172 KB
c2.txt AC 744 ms 13172 KB
d1.txt AC 763 ms 13172 KB
d2.txt AC 741 ms 13172 KB
d3.txt AC 754 ms 13172 KB
d4.txt RE 862 ms 13172 KB
e1.txt AC 771 ms 13172 KB
e2.txt AC 789 ms 13172 KB
e3.txt AC 755 ms 13172 KB
e4.txt RE 865 ms 13172 KB
f1.txt AC 471 ms 3956 KB
f2.txt AC 473 ms 3956 KB
sample1.txt RE 97 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
subtask_a1.txt AC 2 ms 256 KB
subtask_a2.txt AC 2 ms 256 KB
subtask_a3.txt AC 2 ms 256 KB
subtask_a4.txt AC 2 ms 256 KB
subtask_a5.txt AC 2 ms 256 KB
subtask_a6.txt RE 102 ms 256 KB
subtask_b1.txt AC 2 ms 256 KB
subtask_b2.txt AC 2 ms 256 KB
subtask_c1.txt AC 2 ms 256 KB
subtask_c2.txt RE 99 ms 256 KB
subtask_d1.txt AC 2 ms 256 KB
subtask_d2.txt AC 2 ms 256 KB
subtask_d3.txt AC 2 ms 256 KB
subtask_d4.txt AC 2 ms 256 KB
subtask_e1.txt RE 99 ms 256 KB
subtask_e2.txt AC 2 ms 256 KB
subtask_e3.txt AC 2 ms 256 KB
subtask_e4.txt AC 2 ms 256 KB
subtask_f1.txt AC 2 ms 256 KB
subtask_f2.txt AC 2 ms 256 KB