Submission #1413404
Source Code Expand
#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 |
|
|
|
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 |