# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
399756 | Sorting | Martian DNA (BOI18_dna) | C++17 | 39 ms | 2720 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
template<typename T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<typename T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
typedef long long ll;
#define all(x) (x).begin(), (x).end()
int read_int();
const int N = 2e5 + 3;
int n, k, r, a[N];
int mn[N], cnt[N], cnt_ok;
void add(int x){
++cnt[x];
if(cnt[x] == mn[x]) ++cnt_ok;
}
void rem(int x){
if(cnt[x] == mn[x]) --cnt_ok;
--cnt[x];
}
bool check(int mid){
fill(cnt, cnt + k, 0);
cnt_ok = k - r;
for(int i = 0; i < mid; ++i)
add(a[i]);
if(cnt_ok == k) return true;
for(int i = mid; i < n; ++i){
add(a[i]);
rem(a[i - mid]);
if(cnt_ok == k) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
n = read_int(), k = read_int(), r = read_int();
for(int i = 0; i < n; ++i)
a[i] = read_int();
for(int i = 0; i < r; ++i){
int b, q;
b = read_int(), q = read_int();
mn[b] = q;
}
int l = 1, r = n + 1;
while(l != r){
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == n + 1) cout << "impossible\n";
else cout << l << "\n";
}
int ptr = N - 1;
char buff[N];
void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; }
int read_int(){
int ret = 0;
for(; buff[ptr] < '0' || buff[ptr] > '9'; next_char());
for(; '0' <= buff[ptr] && buff[ptr] <= '9'; next_char())
ret = 10 * ret + buff[ptr] - '0';
return ret;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |