Cod sursa(job #3260396)

Utilizator cinavalptopscalaCont laptop in scoala cinavalptopscala Data 2 decembrie 2024 10:55:19
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
ifstream fin ("schi.in");
ofstream fout ("schi.out");

const int Dim = 30001;

int AIB[Dim];
int Query(int i) {
    //cout << "Q " << i << ' ' ;
    int s = 0;
    for(;i>0;i-=i&-i)
        s += AIB[i];
    //cout << s << '\n';
    return s;
}
void Update(int i, int v) {
    //cout << "U " << i << ' ' << v << '\n';
    for(;i<Dim;i+=i&-i)
        AIB[i] += v;
}
int BS(int v) {
    int l = 1, r = Dim, m, q;
    do {
        m = (l + r) / 2;
        q = Query(m);
        //cout << "BS " << m << ' ' << q << '\n';
        if(v <= q) r = m;
        else if(v > q) l = m + 1;
    } while(l < r);
    return m + (q < v);
}

int main() {
    stack<int> players;
    int n;
    fin >> n;
    vector<int> results(n);

    for(int i=1; i<=n; ++i) {
        Update(i, 1);
        fin >> players.emplace();
    }
    while(!players.empty()) {
        int pos = BS(players.top());
        //cout << players.top() << ' ' << bs << '\n';
        results[pos-1] = players.size();
        Update(pos, -1);
        players.pop();
    }
    for(const int &p : results)
        fout << p << '\n';
    return 0;
}