이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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... |