Submission #1213999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213999		aykhn	Martian DNA (BOI18_dna)	C++20	100 / 100	24 ms	4932 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 2e5 + 1;
const int mod = 1e9 + 7;

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k, r;
  cin >> n >> k >> r;
  int d[n];
  for (int &i : d) cin >> i;
  vector<int> q(k, 0), cnt(k, 0);
  int bad = r;
  while (r--)
  {
    int a, b;
    cin >> a >> b;
    q[a] = b;
  }
  int res = n + 1;
  for (int r = 0, l = 0; r < n; r++)
  {
    cnt[d[r]]++;
    if (cnt[d[r]] == q[d[r]]) bad--;
    while (!bad && cnt[d[l]] > q[d[l]]) cnt[d[l]]--, l++;
    if (!bad) res = min(res, r - l + 1);
  }
  if (res == n + 1) cout << "impossible\n";
  else cout << res << '\n';
}

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