Submission #754045

#	Time	Username	Problem	Language	Result	Execution time	Memory
754045		HoriaHaivas	Martian DNA (BOI18_dna)	C++14	100 / 100	34 ms	4680 KiB

dna

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

int need[200001];
bool req[200001];
int f[200001];
int v[200001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k,r,i,j,required,pointerdr,pointerst,x,y,mi;
    bool first;
    cin >> n >> k >> r;
    for (i=1; i<=n; i++)
    {
        cin >> v[i];
    }
    for (i=1; i<=r; i++)
    {
        cin >> x >> y;
        need[x]=y;
        req[x]=1;
    }
    pointerst=1;
    pointerdr=1;
    required=0;
    mi=n+1;
    first=true;
    while (pointerdr<=n)
    {
        if (first==false)
        {
            f[v[pointerst]]--;
            if (f[v[pointerst]]==need[v[pointerst]]-1)
                required--;
            pointerst++;
        }
        first=false;
        while (required<r && pointerdr<=n)
        {
            f[v[pointerdr]]++;
            if (f[v[pointerdr]]==need[v[pointerdr]])
                required++;
            pointerdr++;
        }
        while (required>=r)
        {
            f[v[pointerst]]--;
            if (f[v[pointerst]]==need[v[pointerst]]-1)
                required--;
            pointerst++;
        }
        pointerst--;
        f[v[pointerst]]++;
        if (f[v[pointerst]]==need[v[pointerst]])
            required++;
        if (required==r)
        mi=min(mi,pointerdr-pointerst);
    }
    if (mi!=n+1)
        cout << mi;
    else
        cout << "impossible";
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:22:17: warning: unused variable 'j' [-Wunused-variable]
   22 |     int n,k,r,i,j,required,pointerdr,pointerst,x,y,mi;
      |                 ^

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