Submission #855059

#	Time	Username	Problem	Language	Result	Execution time	Memory
855059		NeroZein	Martian DNA (BOI18_dna)	C++17	100 / 100	27 ms	4688 KiB

dna

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k, r;
  cin >> n >> k >> r;
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i]; 
  }
  vector<int> c(k, -1); 
  for (int i = 0; i < r; ++i) {
    int b, q;
    cin >> b >> q;
    c[b] = q; 
  }
  int ok = k - r; 
  vector<int> cnt(k); 
  auto add = [&](int ind, int v) {
    ok -= cnt[a[ind]] >= c[a[ind]];
    cnt[a[ind]] += v;
    ok += cnt[a[ind]] >= c[a[ind]];
  };
  int ans = n + 1; 
  for (int pl = 0, pr = 0; pl < n; ++pl) {//[l, r)
    pr = max(pr, pl); 
    while (pr < n && ok < k) {
      add(pr, 1); 
      pr++; 
    }
    if (ok == k) {
      ans = min(ans, pr - pl); 
    }
    add(pl, -1); 
  }
  if (ans == n + 1) {
    cout << "impossible" << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0;
}

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