Submission #2211427
Source Code Expand
#include <bits/stdc++.h> #include <climits> #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++) #define si(x) int x = scanInt(); #define sll(x) LL x = scanLong(); #define sci(x) int x; scanf("%d", &x); #define scll(x) LL x; scanf("%lld", &x); #define pi(x) printf("%d ", x) #define pll(x) printf("%lld ", x) #define ps(x) printf("%s", x) #define nl printf("\n") #define clr(a) memset(a, 0, sizeof(a)) #define PB push_back #define MP make_pair using namespace std; typedef unsigned int UI; // 32 bit integer typedef long int LI; // 32 bit integer typedef unsigned long int ULI; // 32 bit unsigned integer typedef long long int LL; // 64 bit integer typedef unsigned long long int ULL; // 64 bit unsigned integer typedef long double LD; typedef vector<int> VI; typedef vector<LL> VLL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; LL mod = 1e9+7; /* Fast I/O */ inline int scanInt() { int n = 0; char ch = getchar(); int sign = 1; while(ch < '0' || ch > '9') { if(ch == '-') sign = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { n = (n<<1)+(n<<3)+(int)(ch-'0'); ch = getchar(); } return n*sign; } inline LL scanLong() { LL n = 0; char ch = getchar(); LL sign = 1; while(ch < '0' || ch > '9') { if(ch == '-') sign = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { n = (n<<1)+(n<<3)+(LL)(ch-'0'); ch = getchar(); } return n*sign; } const LL MAXN = 2e5+10; LL arr[MAXN], cnt[MAXN], present[MAXN]; int main() { sll(n); sll(m); rep(i, 0, n) { arr[i] = scanLong(); cnt[arr[i]]++; } rep(i, 1, n+1) { LL low = max(0ll, i - cnt[i]); rep(j, low, i) present[j]++; } LL ans = 0; rep(i, 0, n) if(!present[i]) ans++; rep(i, 0, m) { sll(x); sll(y); x--; if(y != arr[x]) { if(y > cnt[y]) { if(present[y-cnt[y]-1] == 0) ans--; present[y-cnt[y]-1]++; } if(arr[x] >= cnt[arr[x]]) { if(present[arr[x]-cnt[arr[x]]] == 1) ans++; present[arr[x]-cnt[arr[x]]]--; } cnt[arr[x]]--; cnt[y]++; arr[x] = y; } pll(ans); nl; } }
Submission Info
Submission Time | |
---|---|
Task | C - Snuke and Spells |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2180 Byte |
Status | AC |
Exec Time | 81 ms |
Memory | 6272 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 | 66 ms | 6272 KB |
a2.txt | AC | 66 ms | 6272 KB |
a3.txt | AC | 66 ms | 6272 KB |
a4.txt | AC | 77 ms | 6272 KB |
a5.txt | AC | 65 ms | 6144 KB |
a6.txt | AC | 81 ms | 6272 KB |
b1.txt | AC | 65 ms | 6272 KB |
b2.txt | AC | 65 ms | 6272 KB |
c1.txt | AC | 66 ms | 6272 KB |
c2.txt | AC | 66 ms | 6272 KB |
d1.txt | AC | 65 ms | 6272 KB |
d2.txt | AC | 65 ms | 6272 KB |
d3.txt | AC | 71 ms | 6272 KB |
d4.txt | AC | 71 ms | 6272 KB |
e1.txt | AC | 70 ms | 6272 KB |
e2.txt | AC | 69 ms | 6272 KB |
e3.txt | AC | 67 ms | 6272 KB |
e4.txt | AC | 65 ms | 6272 KB |
f1.txt | AC | 50 ms | 5888 KB |
f2.txt | AC | 50 ms | 5888 KB |
sample1.txt | AC | 2 ms | 2304 KB |
sample2.txt | AC | 2 ms | 2304 KB |
sample3.txt | AC | 2 ms | 2304 KB |
subtask_a1.txt | AC | 2 ms | 2304 KB |
subtask_a2.txt | AC | 2 ms | 2304 KB |
subtask_a3.txt | AC | 2 ms | 2304 KB |
subtask_a4.txt | AC | 1 ms | 2304 KB |
subtask_a5.txt | AC | 2 ms | 2304 KB |
subtask_a6.txt | AC | 2 ms | 2304 KB |
subtask_b1.txt | AC | 2 ms | 2304 KB |
subtask_b2.txt | AC | 2 ms | 2304 KB |
subtask_c1.txt | AC | 1 ms | 2304 KB |
subtask_c2.txt | AC | 2 ms | 2304 KB |
subtask_d1.txt | AC | 2 ms | 2304 KB |
subtask_d2.txt | AC | 1 ms | 2304 KB |
subtask_d3.txt | AC | 1 ms | 2304 KB |
subtask_d4.txt | AC | 2 ms | 2304 KB |
subtask_e1.txt | AC | 2 ms | 2304 KB |
subtask_e2.txt | AC | 2 ms | 2304 KB |
subtask_e3.txt | AC | 1 ms | 2304 KB |
subtask_e4.txt | AC | 1 ms | 2304 KB |
subtask_f1.txt | AC | 2 ms | 2304 KB |
subtask_f2.txt | AC | 2 ms | 2304 KB |