Submission #388820

#	Time	Username	Problem	Language	Result	Execution time	Memory
388820		Nordway	Martian DNA (BOI18_dna)	C++17	100 / 100	39 ms	4512 KiB

dna

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=2e5+500;
const int M=1e6+1;
const ll inf=2e9+11;
const ld EPS=1e-6;
const int INF=1e9;
const ll mod=998244353/*1e9+7*/;
const int dx[4]={1,0,0,-1};
const int dy[4]={0,1,-1,0};

int a[N],b[N],c[N];

void solve(){
  int n,k,m;
  cin>>n>>k>>m;
  for(int i=1;i<=n;i++){
    cin>>a[i];
  }
  for(int i=0;i<k;i++){
    b[i]=-inf;
  }
  for(int i=1;i<=m;i++){
    int x,y;
    cin>>x>>y;
    b[x]=y;
  }
  int l=1;
  int cnt=0;
  int ans=inf;
  for(int r=1;r<=n;r++){
    c[a[r]]++;
    if(c[a[r]]==b[a[r]])cnt++;
    while(c[a[l]]>b[a[l]]){
      c[a[l]]--;
      l++;
    }
    if(cnt==m)ans=min(ans,r-l+1);
  }
  if(ans==inf)cout<<"impossible";
  else cout<<ans;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int T=1;
  //cin>>T;
  for(int i=1;i<=T;i++){
    solve();
    cout<<nl;
  }
  return 0;
}

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