제출 #841822

#제출 시각아이디문제언어결과실행 시간메모리
841822WLZLottery (CEOI18_lot)C++17
100 / 100
397 ms12544 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, l; cin >> n >> l; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int q; cin >> q; vector< pair<int, int> > queries; for (int i = 0; i < q; i++) { int k; cin >> k; queries.emplace_back(k, i); } sort(queries.begin(), queries.end()); vector< vector<int> > ans(n, vector<int>(q, 0)); vector<int> add_to(n, -1); for (int i = 0; i <= l; i++) { auto it = lower_bound(queries.begin(), queries.end(), make_pair(i, -1)); if (it != queries.end()) add_to[i] = it - queries.begin(); } for (int k = 1; k <= n - l; k++) { int cnt = 0; for (int i = 0; i < l; i++) if (a[i] == a[i + k]) cnt++; for (int i = 0, j = k; j <= n - l; i++, j++) { if (add_to[l - cnt] != -1) ans[i][add_to[l - cnt]]++, ans[j][add_to[l - cnt]]++; cnt -= (a[i] == a[j]); if (j + l < n) cnt += (a[i + l] == a[j + l]); } } #ifdef DEBUG //for (auto &[k, i, j] : v) cerr << k << ": " << i << ' ' << j << endl; #endif for (int i = 0; i < n; i++) { for (int j = 1; j < q; j++) ans[i][j] += ans[i][j - 1]; } vector< vector<int> > ans2(q); for (int i = 0; i < q; i++) { vector<int> tmp; for (int j = 0; j <= n - l; j++) tmp.push_back(ans[j][i]); ans2[queries[i].second] = tmp; } swap(ans, ans2); for (int i = 0; i < q; i++) { for (int j = 0; j <= n - l; 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...