Submission #643564

#	Time	Username	Problem	Language	Result	Execution time	Memory
643564		gun_gan	Martian DNA (BOI18_dna)	C++17	100 / 100	164 ms	14728 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:28: 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