This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int t, n, m, k, b, q, r, a[1000005], num[1000005], dem[1000005], mod = 1e9 + 7;
string s;
mt19937_64 rng;
bool flag[1000005];
int mul(int x, int y){
if(y == 0) return 1;
int ans = mul(x, y / 2);
if(y % 2 == 0) return (ans * ans) % mod;
else return (((ans * ans) % mod) * x) % mod;
}
void solve(){
while(r--){
cin >> b >> q;
num[b] = q;
}
int l = 0; r = n + 1;
while(r - l > 0){
int mid = l + r >> 1, ans = 0, answer = 0;
memset(dem, 0, sizeof(dem));
memset(flag, 0, sizeof(flag));
int cnt = 0;
// cout << mid << "\n";
for(int i = 1; i <= n; i++){
dem[a[i]]++;
if(dem[a[i]] >= num[a[i]]){
if(!flag[a[i]]) flag[a[i]] = 1, ans++;
}
if(i > mid){
if(dem[a[i - mid]] == num[a[i - mid]]){
if(flag[a[i - mid]]) flag[a[i - mid]] = 0, ans--;
}
dem[a[i - mid]]--;
}
answer = max(answer, ans);
// cout << ans <<" ";
}
for(int i = 1; i <= n; i++) dem[a[i]]++;
for(int i = 0; i < k; i++){
if(!num[i] && !dem[i]) answer++;
}
// cout << "\n";
if(answer < k) l = mid + 1;
else r = mid;
}
if(r == n + 1) cout << "impossible";
else cout << r;
}
signed main(){
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
rng.seed((int)main ^ time(0));
#ifdef Kawaii
auto starttime = chrono::high_resolution_clock::now();
#endif
cin >> n >> k >> r;
for(int i = 1; i <= n; i++) cin >> a[i];
solve();
#ifdef Kawaii
auto endtime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
cout << "\n=====" << "\nUsed: " << duration << " ms\n";
#endif
}
Compilation message (stderr)
dna.cpp: In function 'void solve()':
dna.cpp:25:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int mid = l + r >> 1, ans = 0, answer = 0;
| ~~^~~
dna.cpp:28:13: warning: unused variable 'cnt' [-Wunused-variable]
28 | int cnt = 0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |