sol informatics №934 91p. fast sort

#include <iostream>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <string>
#include <stack>
#include <time.h>
#include <random>
#include <unordered_set>
#include <queue>
using namespace std;

#define ll long long
#define cin in
#define cout out
#define pii pair<int, int>
#define ld long double
#define u_set unordered_set
#define uid uniform_int_distribution

ifstream in("input.txt");
ofstream out("output.txt");

int H, W, n, cur_h = 1, sz = 0;
const int TREE_SZ = 524288, INF = 2e9;
int tree[TREE_SZ];

struct line{
    int len, h;
    line() : len(W), h(cur_h++) {}
};

//size of 'lines' = cur_h-1 in the beginning of each block
vector<line> lines;

void upd(int v) {
    int l = tree[2*v];
    int r = tree[2*v+1];
    if(r == INF || (l != INF && lines[l].h < lines[r].h))
        tree[v] = l;
    else
        tree[v] = r;
}

void build(int v, int lb, int rb) {
    if(lb == rb) {
        tree[v] = lb;
        return;
    }

    int mid = (lb + rb)/2;
    build(2*v, lb, mid);
    build(2*v+1, mid+1, rb);

    upd(v);
}

void rebuild() {
    fill(tree, tree+TREE_SZ, INF);
    build(1, 0, sz-1);
}

void del(int v, int lb, int rb, int pos) {
    if(lb == rb && rb == pos) {
        tree[v] = INF;
        return;
    }

    int mid = (lb + rb)/2;
    if(pos <= mid)
        del(2*v, lb, mid, pos);
    else
        del(2*v+1, mid+1, rb, pos);

    upd(v);
}

void del(int pos) {
    del(1, 0, sz-1, pos);
}

int get_min(int v, int l, int r, int lb, int rb) {
    if(l > rb || r < lb)
        return INF;

    if(lb == l && rb == r)
        return tree[v];

    int mid = (lb + rb)/2;

    int l_p = get_min(2*v, l, min(mid, r), lb, mid);
    int r_p = get_min(2*v+1, max(mid+1, l), r, mid+1, rb);

    if(r_p == INF || (l_p != INF && lines[l_p].h < lines[r_p].h))
        return l_p;
    else
        return r_p;
}

int get_min(int l, int r) {
    return get_min(1, l, r, 0, sz-1);
}

//finds first num that has more or equal 'len' than 'a' and returns its position in the array
int bin_search(int a) {
    if(lines.back().len < a)
        return -1;

    int l = -1, r = sz - 1;

    while(r - l > 1) {
        int mid = (l+r)/2;
        if(lines[mid].len >= a)
            r = mid;
        else
            l = mid;
    }

    return r;
}

class Compare{
public:
    bool operator()(const line &a, const line &b) const {
        return a.len < b.len;
    }
};

void resort(vector<line> &taken, vector<int> &poses) {
    int p = 0;
    for(int i: poses)
        lines[i] = taken[p++];

    for(; p < taken.size(); p++)
        lines.push_back(taken[p]);

    sort(lines.begin(), lines.end(), Compare());
    sz = (int)lines.size();
}

vector<int> queries;

void gen() {
    int len = (int) sqrt(n) + 1;

    for(int bl = 0; bl <= len; bl++) {
        vector<line> taken;
        vector<int> poses;

        for(int i = bl*len; i < min(n, (bl+1) * len); i++) {

            int cur_w = queries[i];

            int tree_min = INF;

            if(sz > 0) {
                int p = bin_search(cur_w);
                if(p != -1)
                    tree_min = get_min(p, sz-1);
            }

            //минимальный подходящий из taken
            int taken_pos = -1, taken_min = INF;
            for(int j = 0; j < taken.size(); j++) {
                line x = taken[j];

                if(x.len >= cur_w && x.h < taken_min) {
                    taken_pos = j;
                    taken_min = x.h;
                }
            }

            int ans = -1;

            if(taken_min == INF && tree_min == INF) {
                if(cur_h > H || cur_w > W)
                    ans = -1;
                else {
                    ans = cur_h;

                    taken.push_back(line());
                    taken.back().len -= cur_w;
                }
            }
            else if(tree_min == INF || taken_min < lines[tree_min].h) {
                taken[taken_pos].len -= cur_w;
                ans = taken_min;
            }
            else {
                ans = lines[tree_min].h;

                taken.push_back(lines[tree_min]);
                taken.back().len -= cur_w;

                poses.push_back(tree_min);

                lines[tree_min].h = INF;

                del(tree_min);
            }

            cout << ans << '\n';
        }

        if(!taken.empty()) {
            resort(taken, poses);
            rebuild();
        }
    }
}

void input() {
    cin >> H >> W >> n;
    queries.resize(n);
    for(int &x : queries)
        cin >> x;

    for(int i = 0; i < TREE_SZ; i++)
        tree[i] = INF;
}

int main()
{
    input();
    gen();
}