제출 #437747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437747		definitelynotmee	Lottery (CEOI18_lot)	C++98	100 / 100	2466 ms	8160 KiB

lot

#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;

}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20