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
bool debug = false;
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, k, r, temp; cin >> n >> k >> r;
vector<int> v(n);
for (int i = 0 ;i < n; ++i){
cin >> v[i];
}
vector<int> val(k);
for (int i = 0;i < r; ++i){
cin >> temp;
cin >> val[temp];
}
int lo = 0, hi = n, mid = (lo + hi)/2;
while (lo != mid){
if(debug) cout << mid << '\n';
temp = 0;
vector<int> cur(n, 0);
vector<bool> full(k,false);
for (int i = 0; i < mid; ++i){
cur[v[i]]++;
if(cur[v[i]] == val[v[i]]){
full[v[i]] = true;
temp++;
}
}
if(temp == r){
hi = mid;
mid = (lo + hi)/2;
continue;
}
for (int i = mid; i < n; ++i){
cur[v[i]]++;
cur[v[i-mid]]--;
if (v[i] != v[i-mid]){
if(cur[v[i]] == val[v[i]]){
full[v[i]] = true;
temp++;
}
if (cur[v[i-mid]] == val[v[i-mid]]-1){
full[v[i-mid]] = false;
temp--;
}
}
if(temp == r){
hi = mid;
mid = (lo + hi)/2;
continue;
}
}
lo = mid+1;
mid = (lo + hi)/2;
}
if (temp != r && mid == n)cout << "impossible";
else cout << mid;
}
# | 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... |