제출 #1310445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310445		kamal618	Martian DNA (BOI18_dna)	C++20	100 / 100	70 ms	11116 KiB

dna

#include<bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
#define pb push_back
#define pp pop_back
const int N=1e6+9;
const ll inf=1e18 ;
const ll mod = 1e9+9 ;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,k,q,cnt[N],freq[N],freq1[N],x[N],y[N],a[N],l,r;
map<ll,ll>mp1;
map<ll,ll>mp;
bool b=0;
int main()
{
    fast;
    ll ans=inf;
    cin>>n>>k>>q;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    set<ll>st;
    for(ll i=0;i<q;i++){
        cin>>x[i]>>y[i];
        freq1[x[i]]+=y[i];
        st.insert(x[i]);
    }
    for(ll i=0; i<n; i++){
        freq[a[i]]++;
      if(freq[a[i]]==freq1[a[i]])st.erase(a[i]);
      while(freq[a[l]]>freq1[a[l]]) {
            freq[a[l]]--;
            l++;
      }
      if(st.empty())ans=min(ans,i-l);
    }
    if(ans==inf)cout<<"impossible";
    else cout<<ans+1;
    return 0;
}
                                                                                                                                      

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