Submission #948195

#	Time	Username	Problem	Language	Result	Execution time	Memory
948195		NourWael	Martian DNA (BOI18_dna)	C++17	100 / 100	47 ms	6992 KiB

dna

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int req[200005];
int freq[200005];
int a[200005];


signed main() {
 
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

    int n,k,rq; cin>>n>>k>>rq;
    for(int i=0; i<n; i++) cin>>a[i];
    
    for(int i=0; i<rq; i++) {
      int x,c; cin>>x>>c;
      req[x] = c;
    }

    int l = 1, r = n, ans = -1;
    while(l<=r) {
      int mid = (l+r)/2;
      int cnt = 0;

      for(int i=0; i<mid; i++) {
         freq[a[i]]++;
         if(req[a[i]] && freq[a[i]]==req[a[i]]) cnt++; 
      }
     
      bool f = 0;
      int ind = 0;
      for(int i=mid; i<n; i++) {
         if(cnt==rq) { f = 1; break; }
         if(req[a[ind]] && freq[a[ind]]==req[a[ind]]) cnt--; 
         freq[a[ind]]--, freq[a[i]]++;
         if(req[a[i]] && freq[a[i]]==req[a[i]]) cnt++; 
         ind++;
      }
      if(cnt==rq) f = 1;
      
      if(f) { r = mid-1; ans = mid; }
      else l = mid+1;
      for(int i=0; i<=k; i++) freq[i]=0;
    }

    if(ans==-1) cout<<"impossible";
    else cout<<ans;
   return 0;
}

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