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