Submission #1003051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003051		daffuwu	Martian DNA (BOI18_dna)	C++14	100 / 100	26 ms	3932 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, k, r, b, q, cnt[200069], d[200069], cvio, ans = 1e9;

void chg(int x, int y)
{
    int prev = cnt[x];
    cnt[x] += y;
    if (prev == -1 && cnt[x] == 0) cvio--;
    else if (prev == 0 && cnt[x] == -1) cvio++;   
}

int main() 
{
    int i, j;
    scanf("%d%d%d", &n, &k, &r);
    for (i=1; i<=n; i++) scanf("%d", d+i);
    for (i=1; i<=r; i++)
    {
        scanf("%d%d", &b, &q);
        cnt[b] = -q;
        cvio++;
    }
    for (i=1, j=1; i<=n; i++)
    {
        chg(d[i], 1);
        for (; j<i && cvio == 0; chg(d[j++], -1));
        for (;j>1 && cvio>0; chg(d[--j], 1));
        if (cvio == 0) ans = min(ans, i-j+1);
    }
    if (ans == 1e9) printf("impossible\n");
    else printf("%d\n", ans);  
}

Compilation message (stderr)

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

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