# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
399754 | Sorting | Martian DNA (BOI18_dna) | C++17 | 71 ms | 4592 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 0;
char buff[N];
void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; }
int read_int(){
int x;
cin >> x;
return x;
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;
}
컴파일 시 표준 에러 (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... |