Submission #1023920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023920		cleptopod	Martian DNA (BOI18_dna)	C++17	100 / 100	181 ms	13396 KiB

dna

/**
 *    author: tourist
 *    created:
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, r;
  cin >> n >> k >> r;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> reqs(k);
  for (int i = 0; i < r; i++) {
    int x, y;
    cin >> x >> y;
    reqs[x] = y;
  }
  multiset<int> st;
  for (int i = 0; i < k; i++) {
    st.insert(-reqs[i]);
  }
  vector<int> f(k);
  int j = 0, mn = n + 1;
  for (int i = 0; i < n; i++) {
    while (j < n && *st.begin() < 0) {
      st.erase(st.find(f[a[j]] - reqs[a[j]]));
      ++f[a[j]];
      st.insert(f[a[j]] - reqs[a[j]]);
      j++;
    }
    if (*st.begin() >= 0) {
      mn = min(mn, j - i);
    }
    st.erase(st.find(f[a[i]] - reqs[a[i]]));
    --f[a[i]];
    st.insert(f[a[i]] - reqs[a[i]]);
  }
  assert(mn >= 1);
  if (mn <= n) {
    cout << mn << '\n';
  } else {
    cout << "impossible" << '\n';
  }
  return 0;
}

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