Submission #386221

#	Time	Username	Problem	Language	Result	Execution time	Memory
386221		maximath_1	Martian DNA (BOI18_dna)	C++11	100 / 100	151 ms	5356 KiB

dna

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 200005;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1}; // adj
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

int n, k, r, v[MX];
int st[MX * 4];

void upd(int nd, int cl, int cr, int ps, int val){
	if(ps < cl || cr < ps) return;
	if(cl == cr) return void(st[nd] += val);

	upd(nd * 2, cl, (cl + cr) / 2, ps, val);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, ps, val);
	st[nd] = max(st[nd * 2], st[nd * 2 + 1]);
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> k >> r;
	for(int i = 0; i < n; i ++)
		cin >> v[i];

	for(int a, c, i = 0; i < r; i ++){
		cin >> a >> c;
		upd(1, 0, k - 1, a, c);
	}

	int ans = MX + MX + MX;
	for(int i = 0, j = -1; i < n; i ++){
		for(; j < n && st[1] > 0; upd(1, 0, k - 1, v[++ j], -1));
		if(j >= n) break;

		ans = min(ans, j - i + 1);
		upd(1, 0, k - 1, v[i], 1);
	}

	if(ans > n) cout << "impossible\n";
	else cout << ans << endl;
	return 0;
}

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