제출 #467998

#제출 시각아이디문제언어결과실행 시간메모리
467998ivan_tudorLottery (CEOI18_lot)C++14
0 / 100
495 ms468 KiB
#include<bits/stdc++.h> using namespace std; const int N = 10005; int scor[2][N]; struct queryhelper{ int id; int k; }; short ans[101][N]; int v[N]; int l; int getscor(int x, int y){ int ans = 0; for(int i = 0; i < l; i++){ if(v[x + i] != v[y + i]) ans++; } return ans; } bool cmpl(queryhelper a, queryhelper b){ return a.k < b.k; } int precalc[N]; queryhelper q[N]; int main() { //freopen(".in","r",stdin); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n, qs; cin>>n>>l; for(int i = 1; i<=n; i++) cin>>v[i]; cin>>qs; for(int i =1 ; i<=qs; i++){ int k; cin>>k; q[i] = {i, k}; } sort(q +1, q+qs + 1, cmpl); for(int i = 1; i <= qs; i++){ if(precalc[q[i].k] == 0) precalc[q[i].k] = q[i].id; } for(int i = l; i >= 0; i--){ if(precalc[i] == 0) precalc[i] = precalc[i + 1]; } for(int i = 2; i <= n - l + 1; i++){ scor[1][i] = getscor(1, i); int poz = precalc[scor[1][i]]; ans[poz][1]++; ans[poz][i]++; } for(int i = 2; i <= n - l + 1; i++){ int cur = i % 2, lst = 1 - cur; for(int j = i + 1; j <= n - l + 1; j++){ scor[cur][j] = scor[lst][j - 1] - (v[i - 1] != v[j - 1]) + (v[i + l -1] != v[j + l - 1]); /// scor[i][j] int poz = precalc[scor[cur][j]]; ans[poz][i]++; ans[poz][j]++; } } for(int i = 1; i <= qs ; i++){ if(q[i].id) for(int j = 1; j <= n- l + 1; j++){ ans[q[i].id][j]+= ans[q[i - 1].id][j]; } } for(int i = 1; i <= qs; i++){ for(int j = 1; j <= n- l + 1; j++) cout<<ans[i][j]<<" "; cout<<"\n"; } 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...