Submission #1967301
Source Code Expand
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<functional> #include<stack> #include<queue> #include <iomanip> #include<map> #include<limits> #include<cmath> #include<algorithm> #include<bitset> #include<deque> #include<utility> #include<complex> #include<cstdlib> #include<set> #include<cctype> using namespace std; #define DBG cerr << '!' << endl; #define REP(i,n) for(ll (i) = (0);(i) < (n);++i) #define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i) #define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i)) #define PB push_back #define MP make_pair #define FI first #define SE second #define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;} #define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;} #define ALL(v) v.begin(),v.end() #define Decimal fixed<<setprecision(10) typedef long long ll; typedef vector<int> iv; typedef vector<iv> iiv; typedef vector<string> sv; int mp[440000]; int num[220000]; int main() { int *dp = mp + 220000; int n,m;cin >> n >> m; vector<int> v(n); REP(i,n) { cin >> v[i];v[i]--; dp[v[i]-num[v[i]]]++; num[v[i]]++; } int ret = 0; for(int i = 0; i < n;i++) { if(dp[i] == 0)ret++; } REP(i,m) { int a,b;cin >> a >> b;a--;b--; num[v[a]]--; dp[v[a]-num[v[a]]]--; if(v[a]-num[v[a]] >= 0&&dp[v[a]-num[v[a]]] == 0)ret++; v[a] = b; dp[v[a]-num[v[a]]]++; if(v[a]-num[v[a]] >= 0&&dp[v[a]-num[v[a]]] == 1)ret--; num[v[a]]++; cout << ret << endl; // SHOW1d(v,n); // SHOW1d(dp,n); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Snuke and Spells |
User | seica |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1700 Byte |
Status | AC |
Exec Time | 536 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 | 518 ms | 3712 KB |
a2.txt | AC | 536 ms | 3712 KB |
a3.txt | AC | 521 ms | 3712 KB |
a4.txt | AC | 527 ms | 3712 KB |
a5.txt | AC | 506 ms | 3584 KB |
a6.txt | AC | 507 ms | 3712 KB |
b1.txt | AC | 510 ms | 3712 KB |
b2.txt | AC | 516 ms | 3712 KB |
c1.txt | AC | 515 ms | 3712 KB |
c2.txt | AC | 521 ms | 3712 KB |
d1.txt | AC | 515 ms | 3712 KB |
d2.txt | AC | 527 ms | 3712 KB |
d3.txt | AC | 524 ms | 3712 KB |
d4.txt | AC | 513 ms | 3712 KB |
e1.txt | AC | 518 ms | 3712 KB |
e2.txt | AC | 510 ms | 3712 KB |
e3.txt | AC | 513 ms | 3712 KB |
e4.txt | AC | 515 ms | 3712 KB |
f1.txt | AC | 491 ms | 3840 KB |
f2.txt | AC | 480 ms | 3840 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 | 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 | AC | 2 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 | AC | 2 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 | AC | 2 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 |