# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
444178 | BeanZ | Lottery (CEOI18_lot) | C++14 | 1474 ms | 8396 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// I_Love_LPL 1y0m3d
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 1e4 + 5;
long long mod = 1000007;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 311;
const long double eps = 1e-6;
ll a[N], dp[N][105], Q[N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("tests.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n, l;
cin >> n >> l;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
ll q;
cin >> q;
vector<ll> mem;
for (int i = 1; i <= q; i++){
cin >> Q[i];
mem.push_back(Q[i]);
}
sort(mem.begin(), mem.end());
for (int d = 1; (d + l) <= n; d++){
ll cost = 0;
for (int i = 1; i <= l; i++){
if (a[i] != a[i + d]) cost++;
}
ll id = lower_bound(mem.begin(), mem.end(), cost) - mem.begin();
dp[1][id]++;
dp[1 + d][id]++;
for (int i = 2; (i + d + l - 1) <= n; i++){
if (a[i - 1] != a[i + d - 1]) cost--;
if (a[i + l - 1] != a[i + d + l - 1]) cost++;
id = lower_bound(mem.begin(), mem.end(), cost) - mem.begin();
dp[i][id]++;
dp[i + d][id]++;
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j < q; j++){
dp[i][j] += dp[i][j - 1];
}
}
for (int i = 1; i <= q; i++){
ll idx = lower_bound(mem.begin(), mem.end(), Q[i]) - mem.begin();
for (int j = 1; (j + l - 1) <= n; j++){
cout << dp[j][idx] << " ";
}
cout << endl;
}
}
/*
Ans:
Out:
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |