Submission #1093135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093135		juicy	Martian DNA (BOI18_dna)	C++17	100 / 100	149 ms	143300 KiB

dna

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5, inf = 1e9;

int n, k, r;
int a[N], l[N];
deque<int> dq[N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> r;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i < r; ++i) {
    int b; cin >> b >> l[b];
  }
  set<int> st;
  int res = inf;
  for (int i = 0; i < n; ++i) {
    if (l[a[i]]) {
      dq[a[i]].push_back(i);
      if (dq[a[i]].size() > l[a[i]]) {
        st.erase(dq[a[i]].front());
        dq[a[i]].pop_front();
      }
      if (dq[a[i]].size() == l[a[i]]) {
        st.insert(dq[a[i]].front());
      }
    }
    if (st.size() == r) {
      res = min(res, i - *st.begin() + 1);
    }
  }  
  if (res == inf) {
    cout << "impossible";
  } else {
    cout << res;
  }
  return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:32:27: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |       if (dq[a[i]].size() > l[a[i]]) {
      |           ~~~~~~~~~~~~~~~~^~~~~~~~~
dna.cpp:36:27: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |       if (dq[a[i]].size() == l[a[i]]) {
      |           ~~~~~~~~~~~~~~~~^~~~~~~~~~
dna.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if (st.size() == r) {
      |         ~~~~~~~~~~^~~~

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