Submission #602422

#TimeUsernameProblemLanguageResultExecution timeMemory
602422pakhomoveeLottery (CEOI18_lot)C++17
100 / 100
808 ms8440 KiB
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10000; int a[maxn]; int prv[maxn]; int curr[maxn]; pair<int, int> queries[100]; int answer[101][maxn]; int rev[101]; int lb[maxn + 1]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, l; cin >> n >> l; for (int i = 0; i < n; ++i) { cin >> a[i]; } int q; cin >> q; for (int i = 0; i < q; ++i) { cin >> queries[i].first; queries[i].second = i; } sort(queries, queries + q); for (int i = 0; i < n; ++i) { prv[i] = (a[0] != a[i]); } for (int i = 1; i < l; ++i) { for (int j = 1; j < n; ++j) { curr[j] = prv[j - 1] + (a[i] != a[j]); } memcpy(prv, curr, maxn * sizeof(int)); } fill(lb, lb + maxn + 1, q); for (int i = 0; i <= n; ++i) { for (int j = 0; j < q; ++j) { if (queries[j].first >= i ){ lb[i] = j; break; } } } for (int j = l - 1; j < n; ++j) { int mxQid = lb[curr[j]]; ++answer[mxQid][l - 1]; } for (int i = l; i < n; ++i) { curr[l - 1] = 0; for (int p = 0; p < l; ++p) { if (a[i - p] != a[l - p - 1]) ++curr[l - 1]; } for (int j = l; j < n; ++j) { curr[j] = prv[j - 1] - (a[i - l] != a[j - l]) + (a[i] != a[j]); } memcpy(prv, curr, maxn * sizeof(int)); for (int j = l - 1; j < n; ++j) { int mxQid = lb[curr[j]]; ++answer[mxQid][i]; } } for (int i = 0; i < q; ++i) { for (int j = l - 1; j < n; ++j) { if (i > 0) answer[i][j] += answer[i - 1][j]; } } for (int i = 0; i < q; ++i) { rev[queries[i].second] = i; } for (int i = 0; i < q; ++i) { for (int j = l - 1; j < n; ++j) { cout << answer[rev[i]][j] - 1 << ' '; } cout << '\n'; } }
#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...