Submission #314011

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
314011	2020-10-17 20:25:50	Temmie	Martian DNA (BOI18_dna)	C++17	100 / 100	39 ms	4864 KiB

dna

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  
  int n, k, m; std::cin >> n >> k >> m;
  std::vector <int> a(n);
  for (int& x : a) std::cin >> x;
  std::vector <int> req(n, 0), has(n, 0);
  int cntgood = n;
  for (int i = 0; i < m; i++) {
    int t, h; std::cin >> t >> h;
    req[t] = h;
    cntgood--;
  }
  int ans = 1 << 30;
  for (int l = 0, r = 0; r < n; r++) {
    has[a[r]]++;
    if (has[a[r]] == req[a[r]]) cntgood++;
    while (cntgood == n && has[a[l]] > req[a[l]]) has[a[l++]]--;
    if (cntgood == n) ans = std::min(ans, r - l + 1);
  }
  if (ans == 1 << 30) std::cout << "impossible\n";
  else std::cout << ans << "\n";
  std::cout.flush();
  std::cin >> n;
  
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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