제출 #1290940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290940		ayathk	Martian DNA (BOI18_dna)	C++20	100 / 100	68 ms	6836 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define fi first 
#define se second 
#define int long long 
#define all(a) a.begin(),a.end()
#define pb push_back
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const int lg = 30 ;

void solve(){
    int n,k,q;
    cin>>n>>k>>q;
    int q2 = q;
    
    vector <int> a(n);
    for(int& i : a)cin>>i;

    vector <int> nm(maxn, 0);
    vector <bool> vis(maxn, 0);
    while(q2--){
        int b,c;
        cin>>b>>c;
        nm[b] = c;
        vis[b] = 1;
    }
    int mn = 1e9,cnt = 0;
    int st = 1,en = n,mid;
    while(st <= en){
        mid = (st + en)/2;

        deque <int> tem;
        vector <int> nm2(maxn,0);
        bool pos = 0;
        vector <bool> vis2;
        vis2 = vis;
        cnt = 0;
        for(int i = 0;i < mid;i++){
            if(i < mid)tem.push_back(a[i]);
            nm2[a[i]]++;
            if(nm2[a[i]] >= nm[a[i]] && vis2[a[i]]){
                cnt++;
                vis2[a[i]] = 0;
            }
            if(cnt == q)pos = 1;
        }
        for(int i = mid;i < n;i++){
            if(nm2[tem.front()] == nm[tem.front()])cnt--;
            nm2[tem.front()]--;
            tem.pop_front();
            tem.push_back(a[i]);
            nm2[tem.back()]++;
            if(nm2[tem.back()] == nm[tem.back()]){
                cnt++;
            }

            if(cnt == q){
                pos = 1;
                break;
            }
        }
        if(pos){
            en = mid - 1;
            mn = min(mn, mid);
        }
        else{
            st = mid + 1;
        }
    }
    
    if(mn == 1e9)cout<<"impossible";
    else cout<<mn;
    cout<<'\n';
}
signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int qu;
    qu = 1;
    
    while(qu--){
        solve();
    }
    return 0;
}

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