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, tree2;
- 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()
- {
- // ios::sync_with_stdio(0);
- // cin.tie(0);
- 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);
- tree2.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);
- vector<long long> left(n + m, -1);
- long long l = -1;
- for(long long i = 0; i < n + m; i++)
- {
- cin >> v[i];
- // cout << v[i] << "\n";
- 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];
- // cout << a[i] << " ";
- can[i] = 0;
- l = i;
- }
- else
- left[i] = l;
- }
- if(v[i] < 0)
- mas.push_back({abs(v[i]), i});
- }
- // for(long long i = 0; i < n + m; i++)
- // cout << a[i] << " ";
- sort(mas.begin(), mas.end());
- // for(auto i : mas)
- // cout << i.first << " " << i.second << "\n";
- build(0, 0, n + m, tree);
- for(auto i : mas)
- {
- // cout << i.first << " " << i.second << " " << query(0, 0, n + m, 0, i.second + 1, tree) << " ";
- // cout << query(0, 0, n + m, 0, n + m, tree2) << " " << left[i.second] << "\n";
- if(query(0, 0, n + m, 0, i.second + 1, tree) + min(query(0, 0, n + m, i.second + 1, n + m, tree), 0LL) >= i.first)
- {
- // cout << "1";
- // cout << left[i.second] << "\n";
- long long x = -i.first;
- can[i.second] = 1;
- // if(a[left[i.second]] <= 0)
- // x = -i.first;
- // else
- // {
- // a[left[i.second]] -= i.first;
- //
- // if(a[left[i.second]] < 0)
- // x = a[left[i.second]];
- // }
- // cout << x << "\n";
- add_segment(0, 0, n + m, left[i.second], left[i.second] + 1, x, tree);
- }
- }
- 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