Submission #267236

#	Time	Username	Problem	Language	Result	Execution time	Memory
267236		PeppaPig	Martian DNA (BOI18_dna)	C++14	100 / 100	57 ms	4600 KiB

dna

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, k, r;
int A[N], mn[N], cnt[N], valid;

int main() {
    scanf("%d %d %d", &n, &k, &r);
    for(int i = 1; i <= n; i++) scanf("%d", A + i);
    for(int i = 1, a, b; i <= r; i++) {
        scanf("%d %d", &a, &b);
        mn[a] = b;
    }

    int ans = 1e9;
    for(int i = 1, j = 0; i <= n; i++) {
        ++cnt[A[i]];
        if(mn[A[i]] && cnt[A[i]] == mn[A[i]])
            ++valid;
        while(j + 1 < i) {
            if(cnt[A[j + 1]] - 1 < mn[A[j + 1]])
                break;
            --cnt[A[++j]];
        }
        if(valid == r) ans = min(ans, i - j);
    }
    if(ans == 1e9) printf("impossible\n");
    else printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d %d %d", &n, &k, &r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:12:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |     for(int i = 1; i <= n; i++) scanf("%d", A + i);
      |                                 ~~~~~^~~~~~~~~~~~~
dna.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32