Submission #1073979

#TimeUsernameProblemLanguageResultExecution timeMemory
1073979lftroqLottery (CEOI18_lot)C++14
100 / 100
458 ms8528 KiB
#include <bits/stdc++.h> #define endl '\n' #define fi first #define se second #define sqrt sqrtl using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<pii,pii> piiii; const int N=1e4+5; const int Q=105; int a[N],qu[Q],dp[N][Q],rev[N]; void solve() { int n,l,q; cin >> n >> l; for(int i=1;i<=n;i++) cin >> a[i]; cin >> q; vector<int> v; for(int i=1;i<=q;i++) { cin >> qu[i]; v.push_back(qu[i]); } v.push_back(0);v.push_back(N-1); sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end()); for(int i=0;i<(int)v.size();i++) rev[v[i]]=i; for(int len=1;len<=n-l;len++) { int x=1,y=len+1,d=0,p=0; for(int i=1;i<=l;i++) { d+=(a[x+i-1]!=a[y+i-1]); if(v[p]<d) p++; } // cout << len << ' ' << d << ":" << endl; for(;y<=n-l+1;x++,y++) { dp[x][p]++;dp[y][p]++; // cout << x << ' ' << y << ' ' << d << " " << p << endl; d-=(a[x]!=a[y]); if(v[p]>d) p--; d+=(a[x+l]!=a[y+l]); if(v[p]<d) p++; } // cout << "=============" << endl; } for(int i=1;i<=n;i++) for(int j=1;j<(int)v.size();j++) dp[i][j]+=dp[i][j-1]; for(int i=1;i<=q;i++) { for(int j=1;j<=n-l+1;j++) cout << dp[j][rev[qu[i]]] << ' '; cout << endl; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen("hanhhhh.inp","r",stdin); //freopen("hanhhhh.out","w",stdout); int t=1; //cin >> t; while(t--) solve(); 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...