Submission #932491

#TimeUsernameProblemLanguageResultExecution timeMemory
932491imarn Martian DNA (BOI18_dna)C++14
100 / 100
273 ms17020 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vvi vector<vi> #define vp vector<pii> using namespace std; const int N=2e5+5; unordered_map<ll,int>mp,up; ll a[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,k,R;cin>>n>>k>>R; for(int i=0;i<n;i++)cin>>a[i],mp[a[i]]=0; ll l=1,r=n+1; for(int i=0;i<R;i++){ ll b,q;cin>>b>>q;up[b]=q; } while(l<r){ int m=(l+r)>>1; for(auto it : mp)mp[it.f]=0; for(int i=0;i<m;i++)mp[a[i]]++; int cnt=0;bool ch=0; for(auto it : mp)if(up.find(it.f)!=up.end()&&it.s>=up[it.f])cnt++; if(cnt==R)ch=1; for(int i=m;i<n;i++){ if(up.find(a[i-m])!=up.end()&&mp[a[i-m]]==up[a[i-m]])cnt--; mp[a[i-m]]--; if(up.find(a[i])!=up.end()&&mp[a[i]]==up[a[i]]-1)cnt++; mp[a[i]]++; if(cnt==R)ch=1; }if(ch)r=m; else l=m+1; } if(l==n+1)cout<<"impossible"; else cout<<l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...