제출 #437747

#제출 시각아이디문제언어결과실행 시간메모리
437747definitelynotmeeLottery (CEOI18_lot)C++98
100 / 100
2466 ms8160 KiB
#include <bits/stdc++.h> #define mp make_pair #define mt make_tuple #define ff first #define ss second using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll INFL = (1LL<<62)-1; const int INF = (1<<30)-1; const int MOD = 1e9 + 7; const int MAXN = 1e6+1; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, l; cin >> n >> l; vector<int> v(n,0); for(int i = 0; i < n; i++) cin >> v[i]; int q; cin >> q; vector<pii> queries(q); vector<int> order(q); for(int i = 0; i < q; i++){ cin >> queries[i].ff; queries[i].ss = i; } sort(queries.begin(),queries.end(),[&](pii& a, pii& b){ if(a.ff == b.ff) return a.ss < b.ss; return a.ff < b.ff; }); for(int i = 0; i < q; i++){ order[queries[i].ss] = i; } vector<vector<int>> resp(q,vector<int>(n,0)); function<void(int,int,int)> update = [&](int a, int b, int val){ int ini = 0, fim = q; while(ini!=fim){ int m = (ini+fim)>>1; if(queries[m].ff >= val) fim = m; else ini = m+1; } if(ini!=q){ resp[ini][a]++; resp[ini][b]++; } }; vector<int> diff(n-l+1,0);//vamos calcular a diferença do atual para todos os outros intervalos //base: caso do intervalo [0,l-1] for(int i = 0; i < l; i++){ // para cada membro do intervalo for(int j = i+1; j-i < n-l+1 ; j++){ // para cada um dos outros indices diff[j-i]+= v[i]!=v[j]; //adicionamos ao intervalo que corresponde àquela diferença } } for(int i = 1; i <= n-l; i++){ // atualizando resposta para o caso base update(0,i,diff[i]); } for(int i = 1; i < n-l; i++){ // recorrência for(int j = n-l; j > i; j--){ // para cada intervalo após o atual diff[j] = diff[j-1] - (v[j-1]!=v[i-1]) + (v[i+l-1]!=v[j+l-1]); // [ ( ] ) [ ( ] ) quando passamos para o próximo intervalo podemos ver que toda a parte do meio já era comparada anteriormente, então só temos que mudar as bordas update(i,j,diff[j]); } } for(int i = 1; i < q; i++){ for(int j = 0; j < n-l+1; j++){ resp[i][j]+=resp[i-1][j]; } } for(int i = 0; i < q; i++){ for(int j = 0; j < n-l+1; j++){ cout << resp[order[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...