#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int) x.size()
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a); i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define trav(x, y) for(auto&x:y)
using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using pll=pair<ll, ll>;
using pli=pair<ll, int>;
using vi=vector<int>;
using vl=vector<ll>;
using vpii=vector<pii>;
template<class T> inline bool ckmin(T&a, const T&b) {return b<a?a=b,1:0;}
template<class T> inline bool ckmax(T&a, const T&b) {return b>a?a=b,1:0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl='\n';
const int mxN=2e5+10;
const int MOD=1e9+7;
const ll infLL=1e18;
const ld eps=1e-6;
int n, m, k;
int a[mxN];
int cnt[mxN];
int need[mxN];
int tot=0;
int ans=MOD;
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> k;
F0R(i, n) cin >> a[i];
F0R(i, k){
int b, q; cin >> b >> q;
need[b]+=q;
}
for(int l=0, r=0; l<n; l++){
if(l){
cnt[a[l-1]]--;
if(need[a[l-1]]==cnt[a[l-1]]+1) tot--;
}
while(r<n&&tot<k){
cnt[a[r]]++;
if(need[a[r]]==cnt[a[r]]) tot++;
r++;
}
if(r==n&&tot<k){
break;
}
if(tot==k){
ckmin(ans, r-l);
}
}
if(ans==MOD) cout << "impossible\n";
else cout << ans << nl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
324 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
1476 KB |
Output is correct |
2 |
Correct |
15 ms |
1512 KB |
Output is correct |
3 |
Correct |
16 ms |
1504 KB |
Output is correct |
4 |
Correct |
15 ms |
1488 KB |
Output is correct |
5 |
Correct |
20 ms |
2492 KB |
Output is correct |
6 |
Correct |
14 ms |
1484 KB |
Output is correct |
7 |
Correct |
15 ms |
1676 KB |
Output is correct |
8 |
Correct |
23 ms |
3140 KB |
Output is correct |
9 |
Correct |
18 ms |
2020 KB |
Output is correct |
10 |
Correct |
14 ms |
1504 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
3412 KB |
Output is correct |
2 |
Correct |
31 ms |
3056 KB |
Output is correct |
3 |
Correct |
30 ms |
2760 KB |
Output is correct |
4 |
Correct |
15 ms |
1496 KB |
Output is correct |
5 |
Correct |
37 ms |
3940 KB |
Output is correct |
6 |
Correct |
39 ms |
4512 KB |
Output is correct |
7 |
Correct |
19 ms |
2124 KB |
Output is correct |
8 |
Correct |
24 ms |
2396 KB |
Output is correct |
9 |
Correct |
14 ms |
1488 KB |
Output is correct |
10 |
Correct |
16 ms |
1492 KB |
Output is correct |
11 |
Correct |
16 ms |
1504 KB |
Output is correct |
12 |
Correct |
15 ms |
1484 KB |
Output is correct |
13 |
Correct |
20 ms |
2508 KB |
Output is correct |
14 |
Correct |
14 ms |
1388 KB |
Output is correct |
15 |
Correct |
15 ms |
1612 KB |
Output is correct |
16 |
Correct |
22 ms |
3172 KB |
Output is correct |
17 |
Correct |
19 ms |
1996 KB |
Output is correct |
18 |
Correct |
17 ms |
1508 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
328 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 |
324 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
336 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |