Submission #198094

#	Time	Username	Problem	Language	Result	Execution time	Memory
198094		model_code	Santa Claus (RMI19_santa)	C++17	100 / 100	500 ms	6856 KiB

santa

/**
* user:  efremov-95c
* fname: Andrei
* lname: Efremov
* task:  santa
* score: 100.0
* date:  2019-10-11 06:53:32.782550
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <iomanip>
#include <cassert>
#include <cstring>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 17;
int x[N], h[N], v[N], ans[N];
int tr[N * 2], mod[N * 2];

void push(int v) {
	tr[v] += mod[v];
	if (v < N) {
		mod[v * 2] += mod[v];
		mod[v * 2 + 1] += mod[v];
	}
	mod[v] = 0;
}

void rel(int v) {
	tr[v] = min(tr[v * 2], tr[v * 2 + 1]);
}

void add(int cl, int cr, int d, int v=1, int l=0, int r=N) {
	if (cr <= l || r <= cl) {
		push(v);
		return;
	}
	if (cl <= l && r <= cr) {
		mod[v] += d;
		push(v);
		return;
	}
	push(v);
	add(cl, cr, d, v * 2, l, (l + r) / 2);
	add(cl, cr, d, v * 2 + 1, (l + r) / 2, r);
	rel(v);
}

int main() {
#ifdef ONPC
	freopen("a.in", "r", stdin);
#endif
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t, n;
	cin >> t;
	rep(z, t) {
		memset(mod, 0, N * 2 * sizeof(int));
		memset(tr, 0, N * 2 * sizeof(int));
		cin >> n;
		int mp = -1;
		rep(i, n)
			cin >> x[i];
		rep(i, n) {
			cin >> h[i];
			if (!h[i])
				mp = i;
			ans[i] = -1;
		}
		rep(i, n)
			cin >> v[i];
		multiset<int> ms;
		int rp = mp + 1;
		rep(i, rp)
			add(v[i], N, h[i] * 2 - 1);
		rep(i, n) {
			if (i == rp) {
				add(v[rp], N, h[rp] * 2 - 1);
				rp++;
			}
			while (rp < n && tr[1] < 0) {
				add(v[rp], N, h[rp] * 2 - 1);
				rp++;
			}
			if (tr[1] >= 0) {
				ans[rp - 1] = max(ans[rp - 1], i);
			}
			if (h[i]) {
				auto it = ms.lower_bound(v[i]);
				if (it != ms.end()) {
					add(*it, N, 1);
					ms.erase(it);
				}
				add(v[i], N, -1);
			}
			else {
				ms.insert(v[i]);
			}
		}
		for (int i = mp + 1; i < n; i++)
			ans[i] = max(ans[i], ans[i - 1]);
		rep(i, n) {
			if (ans[i] == -1)
				cout << ans[i] << ' ';
			else
				cout << x[i] * 2 - x[ans[i]] << ' ';
		}
		cout << '\n';
	}
}

• Subtask 1: 100 / 100