Submission #1290922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290922		diyah999	Martian DNA (BOI18_dna)	C++20	0 / 100	61 ms	6712 KiB

dna

#include<bits/stdc++.h>
using namespace std;
#define w long long
#define mod 1000000007


int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);
  
  w n,k,R;
  cin>>n>>k>>R;
  
  vector<w>v(n);
  for(w i=0;i<n;++i)cin>>v[i];
  
  vector<w>needed(n);
  w g=0;
  for(w i=0;i<R;++i){
    w z,c;
    cin>>z>>c;
    needed[z]=c;
    g+=c;
  }
  
  
  w ans=n+1;
  
  
  w l=1,r=n;
  while(l<=r){
    w m=(l+r)/2;
    
    w cnt_of_needed=g,alphabet_needed=k;
    
    vector<w>acquired(n),alphabet(n);
    
    for(w i=0;i<m;++i){
      
      if(alphabet[v[i]]==0){
        alphabet_needed--;
      }
      alphabet[v[i]]++;
      
      
      // cout<<v[i]<<' ';
      if(needed[v[i]]>0){
        
        if(acquired[v[i]]<needed[v[i]]){
          cnt_of_needed--;
        }
        acquired[v[i]]++;
      }
    }
    
    
    // cout<<endl<<cnt_of_needed;
    w i=m;
    while((cnt_of_needed!=0 || alphabet_needed>0 )&& i<n){
      
      if(alphabet[v[i]]==0){
        alphabet_needed--;
      }
      alphabet[v[i]]++;
      
      if(alphabet[v[i-m]]==1){
        alphabet_needed++;
      }
      alphabet[v[i-m]]--;
      
      
      if(needed[v[i]]>0){
        
        if(acquired[v[i]]<needed[v[i]]){
          cnt_of_needed--;
        }
        acquired[v[i]]++;
      }
      
      if(needed[v[i-m]]>0){
        
        if(acquired[v[i-m]]<=needed[v[i]]){
          cnt_of_needed++;
        }
        acquired[v[i-m]]--;
      }
      // cout<<i<<" : "<<m<<' '<<alphabet_needed<<' '<<cnt_of_needed<<endl;
      i++;
    }
    
    
    
    // cout<<m<<endl;
    if(cnt_of_needed==0&&alphabet_needed<=0){
      // cout<<m<<endl;
      ans=min(ans,m);
      r=m-1;
    }else l=m+1;
    
    // cout<<l<<endl;
  }
  
  if(ans==n+1)cout<<"impossible";
  else cout<<ans;
  
  
}

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