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;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define inf LLONG_MAX
#define pb push_back
#define lc 2*pos+1
#define rc 2*pos+2
#define halleluya ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
signed main(){
halleluya
int n,k,re;cin>>n>>k>>re;
int num[n];
map<int,int>req;
map<int,int>freq;
vector<int>jum;
int tot=re;
map<int,int>ad;
for (int i=0;i<n;i++)cin>>num[i];
while (re--){
int x,y;cin>>x>>y;
ad[x]=1;
req[x]=y;
jum.pb(x);
}
// for (int i=0;i<n;i++){
// for (auto x:jum) {
// if (0<i) freq[{i,x}]=freq[{i-1,x}];
// if (x==num[i]) freq[{i,x}]++;
// }
// }
int l=0,r=0;
freq[num[0]]++;
map<int,bool>vis;
int ben=0;
int ans=inf;
while(l<=r && r<n){
bool sal=1;
while (ben<tot && r+1<n){
r++;
freq[num[r]]++;
if (ad[num[r]]){
if (freq[num[r]]>=req[num[r]] && vis[num[r]]==0 ){
vis[num[r]]=1;
// cout<<"namben "<<num[r]<<" di "<<r<<endl;
ben++;
}
}
}
while (ben>=tot && l<r && l+1<n){
ans=min(ans,r-l+1);
// cout<<freq[num[l]]<<endl;
freq[num[l]]--;
if (ad[num[l]]){
// cout<<l<<" "<<r<<" "<<" "<<freq[num[l]]<<" "<<req[num[l]] <<" "<<vis[num[l]]<<" "<<ben<<" ";
if (freq[num[l]]<req[num[l]] && vis[num[l]]){
vis[num[l]]=0;
ben--;
}
// cout<<ben<<endl;
}
l++;
}
r++;
}
if (ans==inf)cout<<"impossible";
else cout<<ans;
}
// impossible -> jumlah kurang atau emang gaada substringnya
// harus consecutive
// constraint r
// cuman perlu shortest
// sliding window?
// cuma save jumlah k
// n*k
Compilation message (stderr)
dna.cpp: In function 'int main()':
dna.cpp:41:14: warning: unused variable 'sal' [-Wunused-variable]
41 | bool sal=1;
| ^~~
# | 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... |