Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- using namespace std;
- typedef long long ll;
- typedef pair <ll, ll> pii;
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
- const int INF = 1e7;
- const ll llINF = 1e17;
- const int mxN = 2e5 + 9;
- const int mxM = 1e5 + 9;
- const int MOD = 1e9 + 7;
- const double pi = acos (-1);
- void setIO (string s) {
- freopen ((s + ".in").c_str(), "r", stdin);
- freopen ((s + ".out").c_str(), "w", stdout);
- return;
- }
- int segTree[4 * mxN], m;
- void buildTree (int v, int l, int r) {
- if (l == r) {
- segTree[v] = m;
- return;
- }
- int mid = (l + r) >> 1;
- buildTree (2 * v, l, mid);
- buildTree (2 * v + 1, mid + 1, r);
- segTree[v] = max (segTree[2 * v], segTree[2 * v + 1]);
- return;
- }
- int getQuery (int v, int l, int r, int val) {
- if (l == r)
- return l;
- int mid = (l + r) >> 1;
- if (segTree[2 * v] >= val) {
- return getQuery (2 * v, l, mid, val);
- } else if (segTree[2 * v + 1] >= val) {
- return getQuery (2 * v + 1, mid + 1, r, val);
- } else return -1;
- }
- void updateTree (int v, int l, int r, int idx, int val) {
- if (l == r) {
- segTree[v] -= val;
- return;
- }
- int mid = (l + r) >> 1;
- if (idx <= mid) {
- updateTree (2 * v, l, mid, idx, val);
- } else updateTree (2 * v + 1, mid + 1, r, idx, val);
- segTree[v] = max (segTree[2 * v], segTree[2 * v + 1]);
- }
- void solve () {
- int n;
- cin >> n >> m;
- int Q;
- cin >> Q;
- n = min (n, Q);
- buildTree (1, 1, n);
- while (Q--) {
- int x;
- cin >> x;
- int res = getQuery (1, 1, n, x);
- if (res == -1) {
- cout << -1 << "\n";
- } else {
- cout << res << "\n";
- updateTree (1, 1, n, res, x);
- }
- }
- return;
- }
- int main () {
- int t = 1;
- //cin >> t;
- ios_base::sync_with_stdio (0);
- cin.tie (0);
- setIO ("billboard");
- //preCalc ();
- while (t--) {
- //initialize common variables
- //go solve
- solve ();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement