Submission #378266

#	Time	Username	Problem	Language	Result	Execution time	Memory
378266		suto	Martian DNA (BOI18_dna)	C++17	0 / 100	40 ms	3436 KiB

dna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef string str;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define pb(x)                       push_back(x)
#define pf(x)                       push_front(x)
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll MAXN = 2e5 + 10;
const ll INF = 1e18 + 10;
const ll LOG = 30;
const ll MOD = 1e9 + 7;

ll poww(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
    	if (b & 1) ans = ans * a % md;
    return ans;
}

ll cnt[MAXN] , h[MAXN] , a[MAXN];

int main(){

	fast_io;
	ll n , k , q;
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++){
        ll x , y;
		cin >> x >> y;
		cnt[x] = y;
	}
	ll l = 1 , r = 0 , ans = INF , pq = 0;
	while (l <= n && r <= n){
		if (pq == q){
			ans = min(ans , r - l + 1);
			if(h[a[l]] == cnt[a[l]]){
                pq --;
			}
			h[a[l]] --;
			l ++;
		}
		else{
			r ++;
			h[a[r]] ++;
			if (h[a[r]] == cnt[a[r]]){
                pq ++;
			}
		}
	}
	if(ans == INF){
        cout << "Impossible";
        return 0;
	}
	cout << ans;

}

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