oj.uz

Submission #378266

# Submission time Handle Problem Language Result Execution time Memory
378266 2021-03-16T11:00:12 Z suto Martian DNA (BOI18_dna) C++17
0 / 100
 40 ms 3436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1900 KB Output is correct
2 Correct 19 ms 1900 KB Output is correct
3 Correct 19 ms 1900 KB Output is correct
4 Correct 15 ms 1900 KB Output is correct
5 Correct 20 ms 2540 KB Output is correct
6 Correct 14 ms 1900 KB Output is correct
7 Incorrect 15 ms 1900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3180 KB Output is correct
2 Correct 35 ms 2796 KB Output is correct
3 Correct 31 ms 2796 KB Output is correct
4 Correct 15 ms 1900 KB Output is correct
5 Incorrect 40 ms 3436 KB Output isn't correct
6 Halted 0 ms 0 KB -