Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #pragma optimization_level 3
- #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
- #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);
- }
- printf("%d%c", ans, '\n');
- }
- if(!taken.empty()) {
- resort(taken, poses);
- rebuild();
- }
- }
- }
- void input() {
- scanf("%d%d%d", &H, &W, &n);
- //cin >> H >> W >> n;
- queries.resize(n);
- for(int &x : queries)
- scanf("%d", &x);
- }
- int main()
- {
- input();
- gen();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement