Submission #927142

#	Time	Username	Problem	Language	Result	Execution time	Memory
927142		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	56 ms	14744 KiB

dna

#pragma GCC optimize("O3", "unroll-loops") // "Ofast" 	
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define f first
#define s second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int N = 1e6 + 5, mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ld eps = 1e-6;

ll add (ll a, ll b) {
	a += b;
	if (a < 0) a += mod;
	if (a >= mod) a -= mod;
	return a;
}

ll mul (ll a, ll b) {
	a *= b;
	if (a >= mod) a %= mod;
	return a;
}   

int n, k, R, a[N], b[N], cnt[N], t[4 * N];

void build (int v = 1, int tl = 0, int tr = k) {
	if (tl == tr) {
		t[v] = b[tl];
		return;
	}
	int tm = tl + tr >> 1;
	build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr);
	t[v] = max(t[v << 1], t[v << 1 | 1]);
}

void upd (int pos, int x, int v = 1, int tl = 0, int tr = k) {
	if (tl == tr) {
		t[v] += x;
		return;
	}
	int tm = tl + tr >> 1;
	if (pos <= tm) upd(pos, x, v << 1, tl, tm);
	else upd(pos, x, v << 1 | 1, tm + 1, tr);
	t[v] = max(t[v << 1], t[v << 1 | 1]);	
}

void solve () {
	cin >> n >> k >> R;
	for (int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
	int K = 0;
	for (int i = 1; i <= R; i++) {
		int x, y;
		cin >> x >> y;
		b[x] = y;
		K += y;
	}
	for (int i = 0; i < k; i++) {
		if (cnt[i] < b[i]) cout << "impossible\n", exit(0);
	}      
	build();
	int l = 1, r = 1, ans = inf;
        upd(a[1], -1);
	while (l <= r && r <= n) {
		while (r <= n && t[1] > 0) r++, upd(a[r], -1);
		if (t[1] == 0) ans = min(ans, r - l + 1);
		upd(a[l], 1), l++; 
	}
	cout << ans;
	cout << '\n';
}

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	cin.tie(0) -> sync_with_stdio(0);
	int test = 1;
	if (testcases) cin >> test;
	for (int cs = 1; cs <= test; cs++) {
		solve();
	}
}

Compilation message (stderr)

dna.cpp: In function 'void build(long long int, long long int, long long int)':
dna.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
dna.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
dna.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

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