Submission #1013798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013798		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	60 ms	4968 KiB

dna

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll, ll>
const ll mxN = 5e5 + 5;
ll mod = 1e9 + 7;
using namespace std;
int fr[mxN];
int req[mxN];
int a[mxN];
int main(){
    int n, k, rq;
    cin >>n>>k>>rq;
    for(int i = 1;i <= n;i++) cin >>a[i];
    for(int i = 1;i <= rq;i++){
        int x;
        cin >>x;
        cin >>req[x];
    }
    int ans = 1e9;
    int l = 1, r = 1;
    int tc = 0;
    while(l <= r && r <= n){
        fr[a[r]]++;
        if(fr[a[r]] == req[a[r]]) tc++;
        if(tc == rq) ans = min(ans, r - l + 1);
        while(tc == rq && l <= r){
            ans = min(ans, r - l + 1);
            fr[a[l]]--;
            if(fr[a[l]] == req[a[l]] - 1) tc--;
            l++;
        }
        r++;
    }
    if(ans != 1e9) cout<<ans;
    else cout<<"impossible";
}

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