Submission #452064

#	Time	Username	Problem	Language	Result	Execution time	Memory
452064		soba	Martian DNA (BOI18_dna)	C++14	100 / 100	955 ms	8344 KiB

dna

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int const N = 2e5+3;
set<int>s;
int reqs[N] , arr[N] , cnt[N] , tmp[N];
int n , k , q , a , b;
bool check(int x)
{
    s.clear();
    memset(tmp , 0 , sizeof tmp);
    int r = x;
    for(int i = 0 ; i < x ; i++)
    {
        tmp[arr[i]]++;
    }
    for(int i = 0 ; i < k ; i++)
    {
        if(reqs[i]>tmp[i])
            s.insert(i);
    }
    if(s.empty())
        return true;
    set<int>::iterator it;
    while(r<n)
    {
        tmp[arr[r]]++;
        tmp[arr[r-x]]--;
        if(tmp[arr[r]]>=reqs[arr[r]] && s.find(arr[r])!=s.end())
        {
            it=s.find(arr[r]);
            s.erase(it);
        }
        if(tmp[arr[r-x]]<reqs[arr[r-x]]&&s.find(arr[r-x])==s.end())
        {
            s.insert(arr[r-x]);
        }
        if(s.empty())
            return true;
        r++;
    }
    return false;
}
int main()
{
    cin >> n >> k >> q;
    for(int i = 0 ; i < n ;i++)
    {
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    bool flag =true;
    int l = 0 , r = n , mid;
    while(q--)
    {
        cin >> a >> b ;
        reqs[a]=b;
        l+=b;
        if(reqs[a]>cnt[a])
            flag=false;
    }
    if(!flag)
    {
        cout << "impossible";
        return 0;
    }
    int ans=n;
    while(l<=r)
    {
        mid=(l+r)>>1;
        //cout << mid << "\n";
        if(check(mid))
        {
            ans=min(ans , mid);
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout << ans ;
    return 0;
}

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