Submission #643515

#	Time	Username	Problem	Language	Result	Execution time	Memory
643515		makanhulia	Martian DNA (BOI18_dna)	C++17	100 / 100	142 ms	14304 KiB

dna

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, k, m, a[N], b[N], t[N], f[N], lst[N];
vector<int> pos[N];
vector<array<int,3>> ranges;

void update(int idx, int v)
{
  for(int i = idx; i <= n; i += i & -i) f[i] += v;
}

int query(int idx) 
{
  int ret = 0;
  for(int i = idx; i > 0; i -= i & -i) ret += f[i];
  return ret;
}

int sum(int l, int r)
{
  return query(r) - query(l - 1);
}

int main() 
{
  cin.tie(0); ios_base::sync_with_stdio(0);

  cin >> n >> k >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]].push_back(i);
  }
  for(int i = 0; i < m; i++) {
    int x, v;
    cin >> x >> v;
    for(int j = 0; j + v - 1 < pos[x].size(); j++) {
      ranges.push_back({pos[x][j + v - 1], pos[x][j], x});
    }
  }
  sort(ranges.begin(), ranges.end());
  int ans = 1e9;
  for(auto [r, l, idx] : ranges) {
    if(l > lst[idx]) {
      if(lst[idx] > 0) update(lst[idx], -1);
      lst[idx] = l;
      update(lst[idx], 1);
    }
    int lf = 1, rg = r, z = -1;
    while(lf <= rg) {
      int mid = (lf + rg) / 2;
      if(sum(mid, r) == m) {
        lf = mid + 1, z = mid;
      } else {
        rg = mid - 1;
      }
    }
    // cout << idx << " " << l << " " << r << " " << sum(1, r) << '\n';
    if(z != -1) ans = min(ans, r - z + 1);
  }

  if(ans == 1e9) {
    cout << "impossible";
  } else {
    cout << ans;
  }
} 

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int j = 0; j + v - 1 < pos[x].size(); j++) {
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~

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