Submission #894251

#	Time	Username	Problem	Language	Result	Execution time	Memory
894251		box	Martian DNA (BOI18_dna)	C++17	100 / 100	33 ms	4844 KiB

dna

#include <iostream>
using namespace std;
 
const int N = 2e5;
 
namespace ds {
int c[N], g[N], z;
 
void add(int x) {
  if (g[x] > 0) z -= ++c[x] == g[x];
}
void rem(int x) {
  if (g[x] > 0) z += c[x]-- == g[x];
}
}  // namespace ds
 
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, k, m;
  cin >> n >> k >> m;
  static int a[N];
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int h = 0; h < m; h++) {
    int i;
    cin >> i;
    cin >> ds::g[i];
  }
  ds::z = m;
  int x = n + 1;
  for (int i = 0, j = 0; i < n; i++) {
    while (j < n && ds::z > 0) ds::add(a[j++]);
    if (ds::z == 0) x = min(x, j - i);
    ds::rem(a[i]);
  }
  if (x == n + 1)
    cout << "impossible\n";
  else
    cout << x << '\n';
  return 0;
}

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