Submission #458057

#	Time	Username	Problem	Language	Result	Execution time	Memory
458057		JovanB	Martian DNA (BOI18_dna)	C++17	100 / 100	71 ms	4456 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int n, k, R;
 
int niz[200005];
int treba[200005];
int br[200005];
 
bool check(int x){
    for(int i=1; i<=k; i++){
        br[i] = 0;
    }
    int cnt = 0;
    for(int i=1; i<=x; i++){
        br[niz[i]]++;
        if(br[niz[i]] == treba[niz[i]]) cnt++;
    }
    if(cnt >= R) return 1;
    for(int i=x+1; i<=n; i++){
        br[niz[i]]++;
        if(br[niz[i]] == treba[niz[i]]) cnt++;
        br[niz[i-x]]--;
        if(br[niz[i-x]] == treba[niz[i-x]]-1) cnt--;
        if(cnt >= R) return 1;
    }
    return 0;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;
 
    cin >> n >> k >> R;
    for(int i=1; i<=n; i++){
        cin >> niz[i];
        niz[i]++;
    }
    for(int i=1; i<=k; i++){
        treba[i] = n+500;
    }
    for(int i=1; i<=R; i++){
        int a, b;
        cin >> a >> b;
        treba[a+1] = b;
    }
    int l = 1, r = n, res = n+1;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid)){
            r = mid-1;
            res = mid;
        }
        else l = mid+1;
    }
    if(res == n+1){
        cout << "impossible\n";
    }
    else cout << res << "\n";
    return 0;
}

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