# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259977 | 2020-08-08T21:27:22 Z | Kenzo_1114 | Lottery (CEOI18_lot) | C++17 | 484 ms | 632 KB |
#include<bits/stdc++.h> using namespace std; const int MAXN = 10010; const int MAXQ = 110; int N, L, Q, q[MAXN], a[MAXN], ans[MAXQ][MAXN], K[MAXN]; int main () { scanf("%d %d", &N, &L); for(int i = 1; i <= N; i++) scanf("%d", &a[i]); scanf("%d", &Q); vector<pair<int, int> > qry; for(int i = 0, k; i < Q; i++) { scanf("%d", &k); qry.push_back(make_pair(k, i)); } sort(qry.begin(), qry.end()); for(int i = 0; i < Q; i++) q[qry[i].second] = i; for(int k = 0, id = 0; k <= L; k++) { while(k > qry[id].first && id < qry.size()) id++; if(id >= qry.size()){ K[k] = MAXQ - 1; continue; } K[k] = id; } for(int j = 1; j + L <= N; j++) { int k = 0; for(int i = 1; i <= L; i++) k += (a[i] != a[i + j]); ans[K[k]][1]++; ans[K[k]][1 + j]++; // printf("(1, %d) = %d\n", 1 + j, k); for(int i = 2; i + j + L - 1 <= N; i++) { k -= (a[i - 1] != a[i + j - 1]); k += (a[i + L - 1] != a[i + j + L - 1]); // printf("(%d, %d) = %d\n", i, i + j, k); ans[K[k]][i]++; ans[K[k]][i + j]++; } } for(int i = 0; i < Q; i++) for(int j = 1; j <= N; j++) ans[i][j] += ans[i - 1][j]; for(int i = 0; i < Q; i++) { for(int j = 1; j + L - 1 <= N; j++) printf("%d ", ans[q[i]][j]); printf("\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 471 ms | 516 KB | Output is correct |
2 | Correct | 484 ms | 512 KB | Output is correct |
3 | Correct | 483 ms | 632 KB | Output is correct |
4 | Incorrect | 447 ms | 632 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 471 ms | 516 KB | Output is correct |
2 | Correct | 484 ms | 512 KB | Output is correct |
3 | Correct | 483 ms | 632 KB | Output is correct |
4 | Incorrect | 447 ms | 632 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |