Submission #685432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
685432	2023-01-24T10:52:04 Z	vovamr	Santa Claus (RMI19_santa)	C++17	100 / 100	287 ms	15740 KB

santa

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct seg {
	int n;
	ve<pii> t;
	seg(int n = 0) : n(n) {
		t.resize(4 * n);
	}
	inline pii mg(const pii &a, const pii &b) {
		pii res;
		res.fi = a.fi + b.fi;
		res.se = min(a.se, a.fi + b.se);
		return res;
	}
	inline void mg(int v) { t[v] = mg(t[2 * v + 1], t[2 * v + 2]); }

	inline void build(int v, int vl, int vr) {
		if (vl == vr) return void(t[v] = {0, 0});
		int m = vl + vr >> 1;
		build(2 * v + 1, vl, m);
		build(2 * v + 2, m + 1, vr);
		mg(v);
	}
	inline void upd(int v, int vl, int vr, int pos, int x) {
		if (vl == vr) {
			t[v].fi += x;
			t[v].se = min(t[v].fi, 0);
			return;
		}
		int m = vl + vr >> 1;
		if (pos <= m) upd(2 * v + 1, vl, m, pos, x);
		else upd(2 * v + 2, m + 1, vr, pos, x);
		mg(v);
	}

	inline int get() { return t[0].se; }
	inline void upd(int pos, int x) { upd(0, 0, n - 1, pos, x); }
	inline void build() { build(0, 0, n - 1); }
};

struct checker {
	int n;
	seg st;
	checker(int n) : n(n) {
		st = seg(n);
		st.build();
	}

	inline void add_gift(int x) {
		st.upd(x, -1);
	}
	inline void del_gift(int x) {
		st.upd(x, +1);
	}
	inline void add_human(int x) {
		st.upd(x, +1);
	}
	inline void del_human(int x) {
		st.upd(x, -1);
	}
	inline bool ok() {
		return st.get() >= 0;
	}

	inline void clear() {
		st.build();
	}
};

inline void solve() {
	int n;
	cin >> n;
	ve<int> x(n), h(n), v(n);
	for (auto &i : x) cin >> i;
	for (auto &i : h) cin >> i;
	for (auto &i : v) cin >> i;

	int ps = n - 1;
	for (int i = n - 1; ~i; --i) {
		if (!h[i]) {
			ps = i;
			break;
		}
	}

	checker s(n + 5);

	int fir_can = -1;
	for (int i = 0; i < n; ++i) {
		if (!h[i]) s.add_gift(v[i]);
		else s.add_human(v[i]);

		if (i >= ps && s.ok()) {
			fir_can = i;
			break;
		}
	}

	if (!~fir_can) {
		for (int i = 0; i < n; ++i) {
			cout << -1 << " ";
		}
		cout << '\n';
		return;
	}

	ve<int> who(n);
	multiset<int> gifts, needed;
	for (int i = 0; i < n; ++i) {
		if (!h[i]) {
			gifts.insert(v[i]);
		}
		else {
			auto it = gifts.lower_bound(v[i]);
			if (it != gifts.end()) {
				who[i] = *it;
				gifts.erase(it);
			}
			else {
				needed.insert(v[i]);
			}
		}
	}

	for (int i = 0; i < fir_can; ++i) cout << -1 << " ";

	for (int i = fir_can, ptr = 0; i < n; ++i) {
		assert(s.ok());
		while (ptr < i) {
			if (h[ptr] == 1) {
				if (who[ptr]) s.del_gift(who[ptr]);
				s.del_human(v[ptr]);

				if (!s.ok()) {
					s.add_human(v[ptr]);
					if (who[ptr]) s.add_gift(who[ptr]);
					break;
				}
			}
			++ptr;
		}
		cout << 2 * x[i] - x[ptr] << " ";

		if (i + 1 < n) {
			assert(h[i + 1] == 1);
			s.add_human(v[i + 1]);
		}
	}
	cout << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

santa.cpp: In member function 'void seg::build(int, int, int)':
santa.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int m = vl + vr >> 1;
      |           ~~~^~~~
santa.cpp: In member function 'void seg::upd(int, int, int, int, int)':
santa.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = vl + vr >> 1;
      |           ~~~^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	6 ms	596 KB	Output is correct
4	Correct	19 ms	968 KB	Output is correct
5	Correct	30 ms	1764 KB	Output is correct
6	Correct	51 ms	2816 KB	Output is correct
7	Correct	99 ms	5284 KB	Output is correct
8	Correct	165 ms	7864 KB	Output is correct
9	Correct	188 ms	10496 KB	Output is correct
10	Correct	287 ms	15740 KB	Output is correct