Submission #1282771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282771		enzy	Lottery (CEOI18_lot)	C++20	45 / 100	491 ms	131072 KiB

lot

#include<bits/stdc++.h>
#define sh short
using namespace std;
const int maxn=1e4+10;
const int maxq=110;
map<int,int>relaciona;
sh qtd[maxn], ans[maxn][maxq], ord_ans[maxn][maxq], help[maxn];
int v[maxn];
vector<sh>passado[maxn], pos[maxn];
int ini(int x, int i){ // qm eh o inicio do intervalo do cara qnd ele eh o i-esimo no vetor 
    return x-i+1;
}
int fim(int x, int i, int l){  // qm eh o fim do intervalo do cara qnd ele eh o i-esimo no vetor 
    return ini(x,i)+l-1;
}
int main(){
    int n, l; cin >> n >> l;
    set<int>s;
    for(int i=1;i<=n;i++){
        cin >> v[i];
        s.insert(v[i]);
    }
    int z=0;
    for(int a : s) relaciona[a]=z++;
    for(int i=1;i<=n;i++) v[i]=relaciona[v[i]];
    relaciona.clear(); s.clear();
    for(int i=1;i<=n;i++) pos[v[i]].push_back(i);
    int q; cin >> q;
    vector<pair<int,int>>queries;
    for(int i=1;i<=q;i++){
        int k; cin >> k;
        queries.push_back({l-k,i}); // l-k => qnts caras eu preciso ter q dão certo
    }
    sort(queries.begin(),queries.end());
    int id=1;
    for(int i=1;i<=l;i++){
        // passar por todo pos e dar ++ nos intervalos correspondentes 
        for(int x : pos[v[i]]){
            //cout << x << " " << ini(x,i) << " " << fim(x,i,l) << endl;  
            if(x>i&&fim(x,i,l)<=n) qtd[ini(x,i)-1]++;
        }
        memset(help,0,sizeof(help));
        for(int j=1;j<=n-l;j++) help[qtd[j]]++;
    }
    for(int j=2;j<=n-l+1;j++) passado[j].push_back(qtd[j-1]);
    //cout << "qtd:" << endl;
    //for(int j=1;j<=n;j++) cout << qtd[j] << " ";
    //cout << endl << endl;
    //for(int j=0;j<=n-l+1;j++) cout << help[j] << " ";
    //cout << endl;
    int at=n-l, last=0;
    for(int j=1;j<=q;j++){
        while(last<queries[j-1].first){
            at-=help[last];
            last++;
        }
        ans[1][j]=at;
    }
    for(int i=2;i<=n-l+1;i++){
        // tirar o i-1
        for(int x : pos[v[i-1]]){
            if(i-1<=l&&x>i-1&&fim(x,i-1,l)<=n) qtd[ini(x,i-1)-1]--;
            if(i-1>l&&x>i-1&&fim(x,l,l)<=n) qtd[ini(x,l)-(i-l)]--;
        }
        /*
        cout << "tirei, ent qtd: " << i << endl;
        for(int j=1;j<=n;j++) cout << qtd[j] << " ";
        cout << endl << endl;
        */
        // colocar o (i+l-1)
        for(int x : pos[v[i+l-1]]){
            //cout << x << " " << ini(x,l) << " " << fim(x,l,l) << endl;
            if(x>i+l-1&&fim(x,l,l)<=n) qtd[ini(x,l)-i]++;
        }
        /*
        cout << "coloquei, ent qtd: " << i << endl;
        for(int j=1;j<=n;j++) cout << qtd[j] << " ";
        cout << endl << endl;
        */
        
        memset(help,0,sizeof(help));
        for(int j=1;j<=n-l-i+1;j++) help[qtd[j]]++;
        for(int j=i+1;j<=n-l+1;j++) passado[j].push_back(qtd[j-i]);
        for(int x : passado[i]) help[x]++;
        passado[i].clear();
        int at=n-l, last=0;
        //for(int j=0;j<=n-l+1;j++) cout << help[j] << " ";
        //cout << endl;
        for(int j=1;j<=q;j++){
            while(last<queries[j-1].first){
                at-=help[last];
                last++;
            }
            ans[i][j]=at;
        }
    }
    for(int i=0;i<queries.size();i++){
        for(int j=1;j<=n-l+1;j++) ord_ans[j][queries[i].second]=ans[j][i+1];
    }
    for(int i=1;i<=q;i++){
        for(int j=1;j<=n-l+1;j++) cout << ord_ans[j][i] << " ";
        cout << endl;
    }
}

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