oj.uz

Submission #519707

# Submission time Handle Problem Language Result Execution time Memory
519707 2022-01-27T05:05:37 Z Ierus Martian DNA (BOI18_dna) C++17
100 / 100
 1885 ms 10752 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
typedef long long ll;
//random_device(rd);
//mt19937 rng(rd());
//const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
//template<class T> T randomize(T mod){
//	return (uniform_int_distribution<T>(0, mod))(rng);
//}

const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 2e5+777;
const int MOD = 1e9+7;
const bool I = 0;
int n, k, r, a[N], need[N], have[N], sum;
int main(){const auto solve=[&]() -> void{
	cin >> n >> k >> r;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	for(int i = 0; i < r; ++i){
		int id, val;
		cin >> id >> val;
		need[id] = val;
	}
	int R = 0, res = INT_MAX;
	for(int L = 1; L <= n; ++L){
		while(R < L - 1){
			if(need[a[R]] == have[a[R]]){
				--sum;
			}
			--have[R];
			++R;
		}
		while(sum < r && R + 1 <= n){
			++R;
			++have[a[R]];
			if(need[a[R]] == have[a[R]]){
				++sum;	
			}
//			cerr << "R: " << R << " have["<<a[R]<<"]: " << have[a[R]]  << " sum: " << sum << '\n';
		}
		if(sum == r)
			res = min(res, R - L + 1);
		cerr << "L: " << L << " R: " << R << " sum: " << sum << '\n';
		if(need[a[L]] == have[a[L]]){
			--sum;
		}
		--have[a[L]];
	}
	if(res == INT_MAX) cout << "impossible";
	else cout << res;
};NFS;int T=1;if(I)cin>>T;while(T--)solve();}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 336 KB Output is correct
2 Correct 32 ms 336 KB Output is correct
3 Correct 33 ms 412 KB Output is correct
4 Correct 33 ms 456 KB Output is correct
5 Correct 32 ms 456 KB Output is correct
6 Correct 35 ms 464 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 6704 KB Output is correct
2 Correct 1621 ms 6720 KB Output is correct
3 Correct 1618 ms 6880 KB Output is correct
4 Correct 1587 ms 6856 KB Output is correct
5 Correct 1585 ms 7940 KB Output is correct
6 Correct 1581 ms 6720 KB Output is correct
7 Correct 1564 ms 6896 KB Output is correct
8 Correct 1583 ms 8496 KB Output is correct
9 Correct 1565 ms 7476 KB Output is correct
10 Correct 1588 ms 6788 KB Output is correct
11 Correct 32 ms 336 KB Output is correct
12 Correct 33 ms 392 KB Output is correct
13 Correct 33 ms 456 KB Output is correct
14 Correct 32 ms 464 KB Output is correct
15 Correct 32 ms 336 KB Output is correct
16 Correct 34 ms 392 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 2 ms 304 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 2 ms 312 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 2 ms 208 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 9484 KB Output is correct
2 Correct 1610 ms 9192 KB Output is correct
3 Correct 1605 ms 8904 KB Output is correct
4 Correct 1619 ms 6740 KB Output is correct
5 Correct 1606 ms 9276 KB Output is correct
6 Correct 1695 ms 10752 KB Output is correct
7 Correct 1694 ms 7944 KB Output is correct
8 Correct 1885 ms 8476 KB Output is correct
9 Correct 1831 ms 6736 KB Output is correct
10 Correct 1767 ms 6752 KB Output is correct
11 Correct 1792 ms 6412 KB Output is correct
12 Correct 1712 ms 6444 KB Output is correct
13 Correct 1608 ms 6836 KB Output is correct
14 Correct 1614 ms 6428 KB Output is correct
15 Correct 1672 ms 6416 KB Output is correct
16 Correct 1619 ms 7316 KB Output is correct
17 Correct 1571 ms 6468 KB Output is correct
18 Correct 1621 ms 6456 KB Output is correct
19 Correct 31 ms 360 KB Output is correct
20 Correct 32 ms 332 KB Output is correct
21 Correct 32 ms 432 KB Output is correct
22 Correct 35 ms 460 KB Output is correct
23 Correct 32 ms 388 KB Output is correct
24 Correct 32 ms 392 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct