답안 #396737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396737	2021-04-30T16:48:25 Z	danielcm585	Martian DNA (BOI18_dna)	C++14	100 / 100	63 ms	2460 KB

dna

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 2e5;
int n, k, r;
int a[N+2], cnt[N+2], need[N+2];

bool can(int mid) {
    memset(cnt,0,sizeof(cnt));
    int get = 0;
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        get += (need[a[i]] && cnt[a[i]] == need[a[i]]);
        if (i-mid >= 1) {
            get -= (need[a[i-mid]] && cnt[a[i-mid]] == need[a[i-mid]]);
            cnt[a[i-mid]]--;
        }
        if (i >= mid && get == r) return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> r;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= r; i++) {
        int b, q; cin >> b >> q;
        need[b] = q;
    }
    int ans = -1;
    for (int l = 1, r = n; l <= r; ) {
        int mid = (l+r)/2;
        if (can(mid)) {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    if (ans == -1) cout << "impossible\n";
    else cout << ans << '\n';
    return 0;
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	1 ms	1100 KB	Output is correct
3	Correct	1 ms	1100 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	1212 KB	Output is correct
6	Correct	1 ms	1100 KB	Output is correct
7	Correct	1 ms	1100 KB	Output is correct
8	Correct	1 ms	1100 KB	Output is correct
9	Correct	1 ms	1100 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1100 KB	Output is correct
2	Correct	2 ms	1100 KB	Output is correct
3	Correct	2 ms	1100 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Correct	2 ms	1100 KB	Output is correct
6	Correct	2 ms	1100 KB	Output is correct
7	Correct	1 ms	1100 KB	Output is correct
8	Correct	1 ms	1100 KB	Output is correct
9	Correct	1 ms	1100 KB	Output is correct
10	Correct	1 ms	1100 KB	Output is correct
11	Correct	2 ms	1100 KB	Output is correct
12	Correct	1 ms	1100 KB	Output is correct
13	Correct	1 ms	1100 KB	Output is correct
14	Correct	1 ms	1100 KB	Output is correct
15	Correct	1 ms	1100 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	1860 KB	Output is correct
2	Correct	35 ms	1888 KB	Output is correct
3	Correct	25 ms	1868 KB	Output is correct
4	Correct	29 ms	1804 KB	Output is correct
5	Correct	37 ms	1868 KB	Output is correct
6	Correct	27 ms	1880 KB	Output is correct
7	Correct	28 ms	1868 KB	Output is correct
8	Correct	46 ms	1928 KB	Output is correct
9	Correct	32 ms	1848 KB	Output is correct
10	Correct	36 ms	1964 KB	Output is correct
11	Correct	2 ms	1100 KB	Output is correct
12	Correct	2 ms	1100 KB	Output is correct
13	Correct	2 ms	1100 KB	Output is correct
14	Correct	2 ms	1100 KB	Output is correct
15	Correct	2 ms	1100 KB	Output is correct
16	Correct	2 ms	1100 KB	Output is correct
17	Correct	2 ms	1100 KB	Output is correct
18	Correct	1 ms	1100 KB	Output is correct
19	Correct	1 ms	1104 KB	Output is correct
20	Correct	1 ms	1100 KB	Output is correct
21	Correct	1 ms	1100 KB	Output is correct
22	Correct	1 ms	1104 KB	Output is correct
23	Correct	1 ms	1100 KB	Output is correct
24	Correct	2 ms	1100 KB	Output is correct
25	Correct	1 ms	1100 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	2128 KB	Output is correct
2	Correct	48 ms	2136 KB	Output is correct
3	Correct	47 ms	2104 KB	Output is correct
4	Correct	18 ms	1888 KB	Output is correct
5	Correct	54 ms	2144 KB	Output is correct
6	Correct	63 ms	2460 KB	Output is correct
7	Correct	33 ms	1876 KB	Output is correct
8	Correct	46 ms	1840 KB	Output is correct
9	Correct	31 ms	1868 KB	Output is correct
10	Correct	35 ms	1804 KB	Output is correct
11	Correct	20 ms	1888 KB	Output is correct
12	Correct	29 ms	1892 KB	Output is correct
13	Correct	38 ms	1908 KB	Output is correct
14	Correct	26 ms	1784 KB	Output is correct
15	Correct	27 ms	1876 KB	Output is correct
16	Correct	52 ms	1868 KB	Output is correct
17	Correct	37 ms	1820 KB	Output is correct
18	Correct	38 ms	1872 KB	Output is correct
19	Correct	2 ms	1100 KB	Output is correct
20	Correct	2 ms	1100 KB	Output is correct
21	Correct	2 ms	1100 KB	Output is correct
22	Correct	2 ms	1100 KB	Output is correct
23	Correct	2 ms	1100 KB	Output is correct
24	Correct	3 ms	1104 KB	Output is correct
25	Correct	1 ms	1100 KB	Output is correct
26	Correct	1 ms	1100 KB	Output is correct
27	Correct	1 ms	1100 KB	Output is correct
28	Correct	1 ms	1100 KB	Output is correct
29	Correct	1 ms	1100 KB	Output is correct
30	Correct	1 ms	1100 KB	Output is correct
31	Correct	2 ms	1100 KB	Output is correct
32	Correct	2 ms	1100 KB	Output is correct
33	Correct	1 ms	1100 KB	Output is correct