Submission #897376

#TimeUsernameProblemLanguageResultExecution timeMemory
8973768pete8Lottery (CEOI18_lot)C++17
25 / 100
226 ms65536 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<float.h> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") using namespace std; //#define int long long #define double long double const int mod=998244353,mxn=1e4,lg=22;//inf=1e18,minf=-1e18,Mxn=100000; int n,k,q; int v[mxn+10],ans[mxn+1][mxn+1]; bitset<mxn+10>qry; vector<int>mp[mxn+10]; map<int,int>pos; int c=0; int32_t main(){ fastio cin>>n>>k; vector<int>com; for(int i=0;i<n;i++)cin>>v[i],com.pb(v[i]); sort(all(com)); unique(all(com)); for(auto i:com)pos[i]=++c; for(int i=0;i<n;i++)v[i]=pos[v[i]]; int cur=0; cin>>q; vector<int>qry(q); for(int i=0;i<q;i++)cin>>qry[i]; vector<int>cnt(2*n+1,0); for(int i=0;i<n;i++)mp[v[i]].pb(i); for(int i=0;i<k;i++)for(auto j:mp[v[i]])cnt[j-i+n]++; for(int i=n+1;i<2*n-k+1;i++)ans[cnt[i]][0]++; int l=0,r=k-1; while(r<n-1){ for(auto j:mp[v[l]])cnt[j+n]--; l++; for(int j=2*n;j>=1;j--)cnt[j]=cnt[j-1]; r++; for(auto j:mp[v[r]])cnt[j-(k-1)+n]++; for(int i=n;i<2*n-k+1;i++)if(i-n!=l)ans[cnt[i]][l]++; } for(int i=n;i>=0;i--)for(int j=0;j<n;j++)ans[i][j]+=ans[i+1][j]; for(auto i:qry){ for(int j=0;j<n-k+1;j++)cout<<ans[k-i][j]<<" "; cout<<'\n'; } return 0; }

Compilation message (stderr)

lot.cpp: In function 'int32_t main()':
lot.cpp:53:6: warning: unused variable 'cur' [-Wunused-variable]
   53 |  int cur=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...