Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- constexpr int MAX = 100010;
- int arr[MAX];
- int tree[4 * MAX], lazy[4 * MAX];
- void build(int node, int ini, int fin)
- {
- if (ini > fin) {
- return;
- }
- if (ini == fin) {
- tree[node] = arr[ini];
- return;
- }
- int mid = ini + (fin - ini) / 2;
- build(2 * node, ini, mid);
- build(2 * node + 1, mid + 1, fin);
- tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
- }
- void update(int node, int ini, int fin, int i, int j, int x, int value)
- {
- if (ini > fin || ini > j || fin < i) {
- return;
- }
- if (lazy[node] != 0) {
- tree[node] += lazy[node];
- if (ini != fin) {
- lazy[2 * node] += lazy[node];
- lazy[2 * node + 1] += lazy[node];
- }
- lazy[node] = 0;
- }
- if (tree[node] > x) {
- tree[node] += value;
- if (ini != fin) {
- lazy[2 * node] += value;
- lazy[2 * node + 1] += value;
- }
- return;
- }
- if (ini == fin) {
- return;
- }
- int mid = ini + (fin - ini) / 2;
- update(2 * node, ini, mid, i, j, x, value);
- update(2 * node + 1, mid + 1, fin, i, j, x, value);
- tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
- }
- int query(int node, int ini, int fin, int i, int j)
- {
- if (ini > fin || ini > j || fin < i) {
- return INT_MAX;
- }
- if (lazy[node] != 0) {
- tree[node] += lazy[node];
- if (ini != fin) {
- lazy[2 * node] += lazy[node];
- lazy[2 * node + 1] += lazy[node];
- }
- lazy[node] = 0;
- }
- if (ini >= i && fin <= j) {
- return tree[node];
- }
- int mid = ini + (fin - ini) / 2;
- int q1 = query(2 * node, ini, mid, i, j);
- int q2 = query(2 * node + 1, mid + 1, fin, i, j);
- return std::min(q1, q2);
- }
- int main( )
- {
- std::ios_base::sync_with_stdio(0);
- std::cin.tie(0);
- std::cout.tie(0);
- int n;
- std::cin >> n;
- std::vector<std::pair<int,int>> v;
- for (int i = 0; i < n; ++i) {
- int test;
- std::cin >> test;
- v.push_back({ test, i + 1 });
- }
- std::sort(v.begin( ), v.end( ));
- for (int i = 0; i < n; ++i) {
- arr[i] = v[i].first;
- }
- build(1, 0, n - 1);
- std::fill(lazy, lazy + (4 * MAX), 0);
- int q;
- std::cin >> q;
- while (q--) {
- int x;
- std::cin >> x;
- update(1, 0, n - 1, 0, n - 1, x, -1);
- }
- for (int i = 0; i < n; ++i) {
- v[i].first = query(1, 0, n - 1, i, i);
- std::swap(v[i].first, v[i].second);
- }
- std::sort(v.begin( ), v.end( ));
- for (int i = 0; i < n; ++i) {
- std::cout << v[i].second << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement