제출 #570195

#제출 시각아이디문제언어결과실행 시간메모리
570195MarcosPauloEversLottery (CEOI18_lot)C++17
45 / 100
3075 ms4944 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 10, MAXQ = 110; int n, l, q; int arr[MAXN]; int bit[MAXN][MAXQ]; int ans[MAXQ][MAXN]; vector<pair<int, int> > qry; int get(int i, int p) { int sum = 0; for(; 0 < p && p < MAXQ; p -= p & -p) sum += bit[i][p]; return sum; } void add(int i, int p) { for(; 0 < p && p < MAXQ; p += p & -p) bit[i][p]++; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> l; for(int i = 0; i < n; i++) cin >> arr[i]; cin >> q; for(int i = 0, k; i < q; i++) cin >> k, qry.emplace_back(k, i); sort(begin(qry), end(qry)); for(int i = 0; i <= n - l; i++) { for(int j = 0; j < i; j++) { int dst = 0; for(int k = 0; k < l; k++) dst += arr[i + k] != arr[j + k]; int qtd = lower_bound(begin(qry), end(qry), make_pair(dst, 0)) - begin(qry); add(i, qtd + 1); add(j, qtd + 1); } } for(int i = 0; i < q; i++) for(int j = 0; j <= n - l; j++) ans[qry[i].second][j] = get(j, i+1); 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...