Submission #383573

#	Time	Username	Problem	Language	Result	Execution time	Memory
383573		haboh	Martian DNA (BOI18_dna)	C++14	100 / 100	119 ms	4588 KiB

dna

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <memory.h>
#include <set>

using namespace std;

#define rep(i, n) for(int i =0;i<(n);i++)
#define per(i, n) for (int i=((int)n-1);i>=0;i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define make_unique(x) { sort(all(x)); x.resize(unique(x.begin(), x.end()) - x.begin()); }
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(x) { cerr << #x << "= " << x << "\n"; }
typedef long long ll;
typedef vector<int>vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;


int cnt[200100];
int cur[200100];

int satisfy = 0;

#pragma region 

void add(int x) {
	if (cur[x] >= cnt[x]) satisfy--;
	cur[x]++;
	if (cur[x] >= cnt[x]) satisfy++;
}

void del(int x) {
	if (cur[x] >= cnt[x]) satisfy--;
	cur[x]--;
	if (cur[x] >= cnt[x]) satisfy++;
}


int main() {
	int n, k, R;
	cin >> n >> k >> R;
	vi a(n);
	rep(i, n) cin >> a[i];
	rep(i, R) {
		int b, q;
		cin >> b >> q;
		cnt[b] = q;
	}
	rep(i, n) if (cur[i] >= cnt[i]) satisfy++;
	
	int r = 0;
	const int inf = 1e9;
	int len = inf;
	rep(l, n) {
		while (r < n && satisfy < n) {
			add(a[r]);
			r++;
		}
		if(satisfy == n) len = min(len, r - l);
		del(a[l]);
	}
	if (len == inf) {
		cout << "impossible\n";
	}
	else {
		cout << len << "\n";
	}
	return 0;
}

Compilation message (stderr)

dna.cpp:42: warning: ignoring #pragma region  [-Wunknown-pragmas]
   42 | #pragma region
      |

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