제출 #455171

#제출 시각아이디문제언어결과실행 시간메모리
455171Nima_NaderiLottery (CEOI18_lot)C++14
100 / 100
940 ms12488 KiB
//In the name of God #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MXN = 1e4 + 10; const ll MXQ = 100 + 10; ll n, k, q; ll A[MXN], f[MXN], Q[MXN]; ll diff[MXN], cnt[MXN]; ll ANS[MXQ][MXN], ps[MXN]; void Save(ll p){ ps[0] = cnt[0]; for(int i = 1; i <= n; i ++) ps[i] = ps[i - 1] + cnt[i]; for(int i = 1; i <= q; i ++) ANS[i][p] += ps[Q[i]]; } int main(){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); cin >> n >> k; for(int i = 1; i <= n; i ++) cin >> A[i]; cin >> q; for(int i = 1; i <= q; i ++) cin >> Q[i]; for(int j = 2; j + k - 1 <= n; j ++){ for(int l = 0; l < k; l ++) diff[j - 1] += (A[1 + l] != A[j + l]); cnt[diff[j - 1]] ++; } Save(1); for(int i = 2; i <= n - k + 1; i ++){ cnt[diff[n - k + 1 - i + 1]] --; for(int t = 1; i + t + k - 1 <= n; t ++){ cnt[diff[t]] --; diff[t] -= (A[i - 1] != A[i + t - 1]); diff[t] += (A[i - 1 + k] != A[i + t - 1 + k]); cnt[diff[t]] ++; } Save(i); } memset(cnt, 0, sizeof cnt), memset(diff, 0, sizeof diff); for(int j = 1; j + k - 1 < n; j ++){ for(int l = 0; l < k; l ++) diff[(n - k + 1) - j] += (A[(n - k + 1) + l] != A[j + l]); cnt[diff[(n - k + 1) - j]] ++; } Save(n - k + 1); for(int i = n - k; i >= 1; i --){ cnt[diff[i]] --; for(int t = 1; t <= i - 1; t ++){ cnt[diff[t]] --; diff[t] += (A[i] != A[i - t]); diff[t] -= (A[i + k] != A[i - t + k]); cnt[diff[t]] ++; } Save(i); } for(int i = 1; i <= q; i ++){ for(int j = 1; j <= n - k + 1; j ++) cout << ANS[i][j] << " \n"[j == n - k + 1]; } return 0; } // N.N wants gold medal !
#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...