제출 #1073961

#제출 시각아이디문제언어결과실행 시간메모리
1073961lftroqLottery (CEOI18_lot)C++14
0 / 100
189 ms4620 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,le,q; cin >> n >> le; 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]); } 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-le+1;len++) { int l=1,r=len+1,d=0,p=0; for(int i=l;i<=le;i++) { d+=(a[i]!=a[i+len]); if(v[p]<d) p++; } // cout << len << ' ' << d << ":" << endl; for(;r+le-1<=n;) { dp[l][p]++;dp[r][p]++; // cout << l << ' ' << r << ' ' << d << " " << p << endl; d-=(a[l]!=a[r]); if(p&&v[p-1]>d) p--; l++;r++; d+=(a[r]!=a[r+le-1]); if(v[p]<d) p++; } // cout << "=============" << endl; } for(int j=1;j<=n;j++) for(int i=1;i<(int)v.size();i++) dp[j][i]+=dp[j][i-1]; for(int i=1;i<=q;i++) { for(int j=1;j<=n-le+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...