Submission #931338

#	Time	Username	Problem	Language	Result	Execution time	Memory
931338		daulet	Martian DNA (BOI18_dna)	C++14	100 / 100	355 ms	27052 KiB

dna

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
#define endl "\n"
#define int ll
#define F first     
#define S second
  //      ||
 //      ||
//      || 
#define db double
// #define ld long double
#define short unsigned short
using namespace std;
const int inf = 1e9,MOD=1e9+7,N=3e5+5,MN=1e9+7;
void solve()  {
  int n,k,R;
  cin>>n>>k>>R;
  vector<int>v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  map<int,int>mp;
  int have=0;
  for(int i=0;i<R;i++){
      int b,q;
    cin>>b>>q;
    mp[b]=q;
  }
  map<int,int>cur;
  int l=0,r=0;
  int mn=inf;
  for(;r<n;r++){
    cur[v[r]]++;
    if(cur[v[r]]==mp[v[r]]){
      have++;
    }
    while(have==R&&l<=r){
      mn=min(mn,r-l+1);
      if(cur[v[l]]==mp[v[l]]){
        have--;
      }
      cur[v[l]]--;
      l++;
    }
  }
  if(mn==inf){
    cout<<"impossible"<<endl;
  }
  else{
    cout<<mn<<endl;
  }
}
signed main() {
    IOS;
    // srand(time(NULL));
    //freopen("input.txt", "r", stdin);  
    // freopen("output.txt", "w", stdout);
    int UwU=1; 
    // cin>>UwU;
    for(int i=1;i<=UwU;i++) {
      // cout<<"Case "<<i<<": "<<endl;
        solve();
      // cout<<endl;
    }
}

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