Submission #891036

#TimeUsernameProblemLanguageResultExecution timeMemory
891036Xiaoyang Martian DNA (BOI18_dna)C++17
0 / 100
66 ms8908 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 1ll<<60 #define rep(i,a,b) for (ll i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define mod 1000000007 #define ALL(x) x.begin(),x.end() #define endl "\n" void inc(ll &a,ll b) {a=(a+b)%mod;} void dec(ll &a,ll b) {a=(a-b+mod)%mod;} int prod(ll a,ll b) {return ll(a)*ll(b)%mod;} int lowbit(ll x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const ll maxn=222222; ll a[maxn]; ll need[maxn]; vector<pll>tmp; ll cnt[maxn]; ll bad[maxn]; ll n,k,r; bool check(ll len){ memset(cnt,0,sizeof cnt); memset(bad,0,sizeof bad); ll amt=0; rep(i,1,len+1)cnt[a[i]]++; rep(i,0,k){ if(cnt[i]<need[i]){ bad[i]=1; amt++; } } if(amt==0)return 1; //cout<<endl; //rep(i,0,k)cout<<i<<" "<<cnt[i]<<endl; //rep(i,0,k)cout<<bad[i]<<" "; //debug(amt); rep(i,2,n+1-len){ //cout<<"-------------"<<endl; cnt[a[i-1]]--; if(cnt[a[i-1]]<need[a[i-1]] and !bad[a[i-1]]){//debug(11); amt++; bad[a[i-1]]=1; } cnt[a[i+len-1]]++; if(cnt[a[i+len-1]]>=need[a[i+len-1]] and bad[a[i+len-1]]){//debug(22); amt--; bad[a[i+len-1]]=0; } //rep(i,0,k)cout<<i<<" "<<cnt[i]<<endl; //rep(i,0,k)cout<<bad[i]<<" "; //debug(amt); if(amt==0){ //debug(i); //debug(i+len); return 1; } } return 0; } int main(){ ios::sync_with_stdio(0); cin.tie(0); //freopen("i.txt","r",stdin); cin>>n>>k>>r; rep(i,1,n+1)cin>>a[i]; rep(i,1,r+1){ ll x,y;cin>>x>>y; tmp.pb(MP(x,y)); need[x]=y; } if(!check(n)){ cout<<"impossible"<<endl; return 0; } ll lo=1,hi=n; //bsta the length while(lo<hi){ ll mid=(lo+hi)>>1; if(check(mid))hi=mid; else lo=mid+1; } cout<<lo<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...