Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- vector<long long> a, tree, add;
- const long long INF = (long long)1e18;
- void build(long long i, long long l, long long r, vector<long long> &t)
- {
- if (r == l + 1)
- tree[i] = a[l];
- else
- {
- long long m = (l + r) / 2;
- build(2 * i + 1, l, m, t);
- build(2 * i + 2, m, r, t);
- t[i] = t[2 * i + 1] + t[2 * i + 2];
- }
- }
- void add_segment(long long i, long long l, long long r, long long ql, long long qr, long long delta, vector<long long> &t)
- {
- if (qr <= l || r <= ql)
- return;
- if (ql <= l && qr >= r)
- {
- add[i] += delta;
- return;
- }
- long long m = (l + r) / 2;
- add_segment(2 * i + 1, l, m, ql, qr, delta, t);
- add_segment(2 * i + 2, m, r, ql, qr, delta, t);
- t[i] = t[2 * i + 1] + add[2 * i + 1] + t[2 * i + 2] + add[2 * i + 2];
- }
- long long query(long long i, long long l, long long r, long long ql, long long qr, vector<long long> &t)
- {
- if (qr <= l || r <= ql)
- return 0;
- if (ql <= l && r <= qr)
- {
- return t[i] + add[i];
- }
- long long m = (l + r) / 2;
- return query(2 * i + 1, l, m, ql, qr, t) + add[i] + query(2 * i + 2, m, r, ql, qr, t);
- }
- main()
- {
- long long n, m;
- cin >> n >> m;
- a.resize(n + m + 1);
- tree.resize(4 * (n + m) + 1, 0);
- add.resize(4 * (n + m) + 1, 0);
- vector<long long> v(n + m);
- vector<pair<long long, long long>> mas;
- vector<long long> can(n + m, -1), left(n + m, -1);
- long long l = -1;
- for(long long i = 0; i < n + m; i++)
- {
- cin >> v[i];
- if(i == 0)
- if(v[i] > 0)
- a[i] = v[i], can[i] = 0, l = i;// ближайшее положительное;
- else
- {
- if(v[i] > 0)
- {
- a[i] = v[i];
- can[i] = 0;
- left[i] = l;// ближайшее положительное
- l = i;
- }
- else
- left[i] = l;
- }
- if(v[i] < 0)
- mas.push_back({abs(v[i]), i});
- }
- sort(mas.begin(), mas.end());// сортируем по значению
- build(0, 0, n + m, tree);
- for(auto i : mas)
- {
- if(query(0, 0, n + m, 0, i.second + 1, tree) >= i.first)// если хватает денег
- {
- long long x = i.first;
- can[i.second] = 1;
- int t = i.second;
- while(x > 0)// пока не уменьшили текущее число
- {
- long long cur = min(x, query(0, 0, n + m, left[i.second], left[i.second] + 1, tree));
- add_segment(0, 0, n + m, left[i.second], left[i.second] + 1, -cur, tree);// уменьшаем ближайшее
- if(query(0, 0, n + m, left[i.second], left[i.second] + 1, tree) == 0)// если текущее равно 0
- {
- int g = i.second;
- i.second = left[i.second]; // следующее ближайшее
- left[g] = left[i.second]; // эвристика сжатия путей.
- left[t] = left[i.second];
- }
- if(left[i.second] == -1)
- break;
- x -= cur;
- }
- }
- }
- for(int i = 0; i < can.size(); i++)
- {
- if(can[i] == 0)
- cout << "resupplied";
- else if(can[i] == -1)
- cout << "declined";
- else
- cout << "approved";
- cout << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement