Submission #666904

#	Time	Username	Problem	Language	Result	Execution time	Memory
666904		divad	Martian DNA (BOI18_dna)	C++14	100 / 100	122 ms	4636 KiB

dna

#include <iostream>
#include <cstring>
#define MAX 200002
using namespace std;
int n,k,r,a[MAX],vf[MAX],t[MAX],x,y;

bool check(int len){
    int cnt = 0;
    memset(vf, 0, sizeof(vf));
    for(int i = 1; i <= len; i++){
        vf[a[i]]++;
        if(vf[a[i]] == t[a[i]]){
            cnt++;
        }
    }
    if(cnt == r){
        return true;
    }
    for(int i = len+1; i <= n; i++){
        if(vf[a[i]]+1 == t[a[i]]){
            cnt++;
        }
        vf[a[i]]++;
        if(vf[a[i-len]] == t[a[i-len]]){
            cnt--;
        }
        vf[a[i-len]]--;
        if(cnt == r){
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> k >> r;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= r; i++){
        cin >> x >> y;
        t[x] = y;
    }
    int ans = -1;
    int st = 1, dr = n;
    /// 0 0 0 1 1 1 1
    ///       ^
    while(st <= dr){
        int mid = (st+dr)/2;
        if(check(mid)){
            ans = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    if(ans == -1){
        cout << "impossible\n";
    }else{
        cout << ans;
    }
    return 0;
}

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