Cod sursa(job #3152661)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 26 septembrie 2023 10:24:10
Problema Sum Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>
#define DIM 200001
#define INF 2e9

using namespace std;

ifstream fin("file.in");
ofstream fout("file.out");

struct nod{

    int answer, deleted, pos;

};

vector <nod> wmt(4 * DIM);

int v[DIM];

nod Combine(nod st, nod dr){

    nod answer;

    answer.answer = min(st.answer, dr.answer);

    if(st.answer <= dr.answer)
        answer.pos = st.pos;
    else answer.pos = dr.pos;

    answer.deleted = st.deleted + dr.deleted;

}

void Update(int node, int st, int dr, int a, int b){

    if(st == dr){

        if(b == INF){

            wmt[node].answer = INF;

            wmt[node].deleted = 0;

            wmt[node].pos = st;

        }

        else {

            wmt[node].answer = b;

            wmt[node].deleted = 1;

            wmt[node].pos = st;

        }

    }

    else {

        int mij = (st + dr) >> 1;

        if(a <= mij)
            Update(node << 1, st, mij, a, b);
        if(a > mij)
            Update(node << 1 | 1, mij + 1, dr, a, b);

        wmt[node] = Combine(wmt[node << 1], wmt[node << 1 | 1]);

    }

}

int Query_sum(int node, int st, int dr, int a, int b){

    if(dr < a || st > b)
        return 0;

    if(st >= a && dr <= b)
        return wmt[node].deleted;

    else {

        int mij = (st + dr) >> 1;

        int ok1 = Query_sum(node << 1, st, mij, a, b);
        int ok2 = Query_sum(node << 1 | 1, mij + 1, dr, a , b);

        return ok1 + ok2;

    }

}

int Query_min(int node, int st, int dr, int a, int b){

    if(dr < a || st > b)
        return INF;

    if(st >= a && dr <= b)
        return wmt[node].answer;

    else {

        int mij = (st + dr) >> 1;

        int ok1 = Query_sum(node << 1, st, mij, a, b);
        int ok2 = Query_sum(node << 1 | 1, mij + 1, dr, a , b);

        return min(ok1, ok2);

    }

}

int get_pos(int node, int st, int dr, int p){

    if(st == dr)
        return st;

    else {

       int mij = (st + dr) >> 1;

       if(wmt[node << 1].deleted >= p)
            return get_pos(node << 1, st, mij, p);
       else return get_pos(node << 1 | 1, mij + 1, dr, p - wmt[node << 1].deleted);

    }

}

int n, k, i, Q, pos;

int main(){

    fin >> Q;

    while(Q--){

        fin >> n >> k;

        for(i=1;i<=n;i++){
            fin >> v[i];
            Update(1, 1, n, i, v[i]);
        }

        for(i=1;i<=n;i++){

            pos = get_pos(1, 1, n, k + 1);

            pos = Query_min(1, 1, n, 1, pos);

            k -= (Query_sum(1, 1, n, 1, pos) - 1);

            Update(1, 1, n, pos, INF);

        }

        fout << "\n";

    }

}