Submission #2701150
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200100; int cnt[N], zeros, kek[N]; int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; ++cnt[a[i]]; } for (int i = n; i >= 1; --i) { for (int j = 0; j < min(cnt[i], i + 1); ++j) { ++kek[i - j]; } } for (int i = 1; i <= n; ++i) { if (!kek[i]) { ++zeros; } } while (m--) { int x, y; cin >> x >> y; --x; if (a[x] - cnt[a[x]] + 1 >= 1) { if (--kek[a[x] - cnt[a[x]] + 1] == 0) { ++zeros; } } --cnt[a[x]]; a[x] = y; if (y - cnt[y] >= 1) { if (++kek[y - cnt[y]] == 1) { --zeros; } } ++cnt[y]; cout << zeros << '\n'; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Snuke and Spells |
User | meatrow |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1145 Byte |
Status | AC |
Exec Time | 86 ms |
Memory | 3840 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 | 83 ms | 3840 KB |
a2.txt | AC | 84 ms | 3840 KB |
a3.txt | AC | 84 ms | 3712 KB |
a4.txt | AC | 83 ms | 3712 KB |
a5.txt | AC | 81 ms | 3712 KB |
a6.txt | AC | 83 ms | 3840 KB |
b1.txt | AC | 82 ms | 3712 KB |
b2.txt | AC | 82 ms | 3712 KB |
c1.txt | AC | 83 ms | 3712 KB |
c2.txt | AC | 83 ms | 3712 KB |
d1.txt | AC | 82 ms | 3712 KB |
d2.txt | AC | 82 ms | 3712 KB |
d3.txt | AC | 82 ms | 3712 KB |
d4.txt | AC | 82 ms | 3712 KB |
e1.txt | AC | 83 ms | 3712 KB |
e2.txt | AC | 83 ms | 3712 KB |
e3.txt | AC | 83 ms | 3712 KB |
e4.txt | AC | 86 ms | 3840 KB |
f1.txt | AC | 65 ms | 3072 KB |
f2.txt | AC | 65 ms | 3072 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 |