Submission #643451

#	Time	Username	Problem	Language	Result	Execution time	Memory
643451		kith14	Martian DNA (BOI18_dna)	C++14	100 / 100	54 ms	6348 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 2e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], need[N], cr[N], cnt[N];
ll x, y, k;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> v;

bool pos(ll key){
  ll rem = k;
  memset(cnt,0,sizeof(cnt));
  repp(i,1,key){
    cnt[ar[i]]++;
    if (cnt[ar[i]] == need[ar[i]]) rem--;
    if (rem == 0) return 1;
  }
  repp(i,key+1,n){
    cnt[ar[i-key]]--;
    if (cnt[ar[i-key]] == need[ar[i-key]]-1) rem++;
    cnt[ar[i]]++;
    if (cnt[ar[i]] == need[ar[i]]) rem--;
    if (rem == 0) return 1;
  }
  return 0;
}

void input(){
  cin >> n >> m >> k;
  repp(i,1,n) cin >> ar[i];
  repp(i,1,k){
    cin >> x >> y;
    br[i] = x, cr[i] = y;
    need[x] = y;
  }
}

void solve(){
  ll l = 1, r = n, ret = -1;
  while(l <= r){
    ll md = (l+r)/2;
    if (pos(md)){
      r = md-1;
      ret = md;
    }
    else l = md+1;
  }
  if (ret == -1) cout << "impossible\n";
  else cout << ret << "\n";
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

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