Submission #1413404


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/
 

int N, M, A[201010];
int C[201010];
int L[201010], R[201010];
int non[201010];
//---------------------------------------------------------------------------------------------------
int ans = 0;
void add(int a) {
    if (non[a]) {
        L[a] = R[a] = a;
        if (C[a] == 0) ans--;
        C[a]++;
        non[a] = 0;
    }
    else {
        L[a]--;
        if (0 < L[a]) {
            if (C[L[a]] == 0) ans--;
            C[L[a]]++;
        }
    }
}
void del(int a) {
    if (L[a] == R[a]) {
        if (C[a] == 1) ans++;
        C[a]--;
        non[a] = 1;
    }
    else {
        if (0 < L[a]) {
            if (C[L[a]] == 1) ans++;
            C[L[a]]--;
        }
        L[a]++;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
 
    ans = N;
    rep(i, 0, N + 1) non[i] = 1;
 
    rep(i, 0, N) add(A[i]);
 
    rep(q, 0, M) {
        int x, y; cin >> x >> y;
        x--;
 
        del(A[x]);
 
        A[x] = y;
 
        add(y);
 
        printf("%d\n", ans);
    }
}

Submission Info

Submission Time
Task C - Snuke and Spells
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2067 Byte
Status AC
Exec Time 95 ms
Memory 5376 KB

Judge Result

Set Name Sample subtask All
Score / Max Score 0 / 0 500 / 500 500 / 500
Status
AC × 3
AC × 23
AC × 46
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 95 ms 5376 KB
a2.txt AC 95 ms 5376 KB
a3.txt AC 94 ms 5376 KB
a4.txt AC 94 ms 5376 KB
a5.txt AC 92 ms 5120 KB
a6.txt AC 95 ms 5376 KB
b1.txt AC 93 ms 5376 KB
b2.txt AC 93 ms 5376 KB
c1.txt AC 95 ms 5376 KB
c2.txt AC 95 ms 5376 KB
d1.txt AC 93 ms 5376 KB
d2.txt AC 93 ms 5376 KB
d3.txt AC 93 ms 5376 KB
d4.txt AC 94 ms 5376 KB
e1.txt AC 94 ms 5376 KB
e2.txt AC 94 ms 5376 KB
e3.txt AC 94 ms 5376 KB
e4.txt AC 94 ms 5376 KB
f1.txt AC 67 ms 3968 KB
f2.txt AC 68 ms 3968 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
subtask_a1.txt AC 1 ms 256 KB
subtask_a2.txt AC 1 ms 256 KB
subtask_a3.txt AC 1 ms 256 KB
subtask_a4.txt AC 1 ms 256 KB
subtask_a5.txt AC 1 ms 256 KB
subtask_a6.txt AC 1 ms 256 KB
subtask_b1.txt AC 1 ms 256 KB
subtask_b2.txt AC 1 ms 256 KB
subtask_c1.txt AC 1 ms 256 KB
subtask_c2.txt AC 1 ms 256 KB
subtask_d1.txt AC 1 ms 256 KB
subtask_d2.txt AC 1 ms 256 KB
subtask_d3.txt AC 1 ms 256 KB
subtask_d4.txt AC 1 ms 256 KB
subtask_e1.txt AC 1 ms 256 KB
subtask_e2.txt AC 1 ms 256 KB
subtask_e3.txt AC 1 ms 256 KB
subtask_e4.txt AC 1 ms 256 KB
subtask_f1.txt AC 1 ms 256 KB
subtask_f2.txt AC 1 ms 256 KB