Submission #483332

#TimeUsernameProblemLanguageResultExecution timeMemory
483332MOUF_MAHMALATLottery (CEOI18_lot)C++14
65 / 100
1720 ms828 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef int ll; const ll mod=1e9+7; ll n,l,q,o,a[10001],c[10001],x,ans; map<ll,ll>mp; vector<vector<ll> >v; int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>l; if(n>2000) { c[0]=1; for(ll i=1; i<=n; i++) c[i]=(1LL*c[i-1]*1021)%mod; for(ll i=0; i<n; i++) cin>>a[i]; for(ll i=0; i+l-1<n; i++) { x=0; for(ll j=i; j<i+l; j++) x=(1LL*x+1LL*c[j-i]*a[j])%mod; mp[x]++; a[i]=x; } cin>>q; while(q--) { cin>>x; for(ll i=0; i+l-1<n; i++) cout<<mp[a[i]]-1<<" "; } return 0; } for(ll i=0; i<n; i++) { cin>>a[i]; if(!mp[a[i]]) mp[a[i]]=++o; a[i]=mp[a[i]]; } mp.clear(); v.resize(o+1); for(ll i=0; i<n; i++) v[a[i]].push_back(i); cin>>q; while(q--) { cin>>x; x=l-x; for(ll i=0; i+l-1<n; i++) { ans=0; memset(c,0,sizeof c); for(ll j=i; j<i+l; j++) { for(auto k:v[a[j]]) { if(k-j+i>=0) c[k-j+i]++; } } for(ll j=0; j+l-1<n; j++) if(i!=j) ans+=(c[j]>=x); cout<<ans<<" "; } cout<<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...
#Verdict Execution timeMemoryGrader output
Fetching results...