Submission #84145

#	Time	Username	Problem	Language	Result	Execution time	Memory
84145		radoslav11	New Home (APIO18_new_home)	C++14	0 / 100	5146 ms	908308 KiB

new_home

/*
   We will use sweep line to solve the problem. We split the stores into 2 queries: 
   1) Add store i at time a[i]
   2) Remove store i at time b[i] + 1
   We will also have queries in the sweep line. Everything will be sorted by time in increasing order.

   Now to handle queries we will maintain K sets - the available positions of j-type stores. Then if A and B are two consecutive stores, the closest elements to all positions in [A; B] are A or B.
   Then let's have a two segment trees wtih sets - one for closest elements to the left and one for closest elements to the right. Now addition of store with type X will be done like that:

   1) Let A <= X <= B and A and B are the closest stores of the same type. Then we will remove -A from the first segment tree and B from the second tree from the interval [A; B]. 
   2) We add -A to [A; X] in the first tree.
   3) We add X to [A; X] in the second tree.
   4) We add -X to [X; B] in the first tree.
   5) We add B to [X; B] in the second tree.

   Now query is simply getting maximum and minimum on the path from root to the corresponding leaf.

   The complexity will be O(N * log N * log N).

   As sets are slow, we will compress the input in each segment tree node beforehand and then use priority queue instead of sets.
   */

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int inf = (int)1e9 + 42;

int n, k, q;

struct event
{
	int type;
	int T, x, tp, idx;

	event() { type = tp = T = x = 0; idx = -1; }
	event(int t, int Tm, int X, int i, int pp = -1)
	{
		type = t;
		T = Tm;
		x = X;
		idx = i;
		tp = pp;
	}
};

bool cmp(event a, event b) 
{ 
	if(a.T != b.T) return a.T < b.T; 
	return a.type < b.type;
}

vector<event> Ev;
int answer[MAXN];

vector<int> Xcord;
int get(int x) { return L_B(ALL(Xcord), x) - Xcord.begin(); }

void read()
{
	cin >> n >> k >> q;

	for(int i = 0; i < n; i++)
	{
		int x, t, a, b;
		cin >> x >> t >> a >> b;
		Ev.push_back(event(0, a, x, i, t));
		Ev.push_back(event(1, b + 1, x, i, t));
		Xcord.push_back(x);
	}

	for(int i = 0; i < q; i++)
	{
		int x, t;
		cin >> x >> t;
		Ev.push_back(event(2, t, x, i));
		Xcord.push_back(x);
	}
}

set<pair<int, int> > ST[MAXN];

void add_mids(int l, int r)
{
	int mid = (l + r) / 2;
	Xcord.push_back(mid);
	Xcord.push_back(mid + 1);
}
	
void prep_compr_add(int y, int x, int i)
{
	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	ST[y].insert({x, i});

	add_mids(bef->first, x);
	add_mids(x, aft->first);
}

void prep_compr_rem(int y, int x, int i)
{
	ST[y].erase({x, i});

	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	add_mids(bef->first, aft->first);
}

struct segment_tree
{
	vector<int> li[4 * MAXN];
	priority_queue<pair<int, int> > q[4 * MAXN];
	vector<int> cnt[4 * MAXN];

	void init(int l, int r, int idx)
	{
		sort(ALL(li[idx]));
		li[idx].erase(unique(ALL(li[idx])), li[idx].end());
		cnt[idx].assign(SZ(li[idx]), 0);

		if(l == r) return;

		int mid = (l + r) >> 1;
		init(l, mid, 2 * idx + 1);
		init(mid + 1, r, 2 * idx + 2);
	}

	void fix(int idx)
	{
		while(!q[idx].empty() && cnt[idx][q[idx].top().second] >= 1)
		{
			cnt[idx][q[idx].top().second]--;
			q[idx].pop();
		}
	}

	void add_to_prep(int ql, int qr, int v, int l, int r, int idx)
	{
		if(ql > r || qr < l)
			return;

		if(ql <= l && r <= qr)
		{
			li[idx].push_back(v);
			return;
		}

		int mid = (l + r) >> 1;
		add_to_prep(ql, qr, v, l, mid, 2 * idx + 1);
		add_to_prep(ql, qr, v, mid + 1, r, 2 * idx + 2);
	}

	void add(int ql, int qr, int v, int l, int r, int idx)
	{
		if(ql > r || qr < l)
			return;

		if(ql <= l && r <= qr)
		{
			int o = L_B(ALL(li[idx]), v) - li[idx].begin();
			q[idx].push({v, o});
			fix(idx);
			return;
		}

		int mid = (l + r) >> 1;
		add(ql, qr, v, l, mid, 2 * idx + 1);
		add(ql, qr, v, mid + 1, r, 2 * idx + 2);
	}

	void rem(int ql, int qr, int v, int l, int r, int idx)
	{
		if(ql > r || qr < l)
			return;

		if(ql <= l && r <= qr)
		{
			int o = L_B(ALL(li[idx]), v) - li[idx].begin();
			cnt[idx][o]++;
			fix(idx);
			return;
		}

		int mid = (l + r) >> 1;
		rem(ql, qr, v, l, mid, 2 * idx + 1);
		rem(ql, qr, v, mid + 1, r, 2 * idx + 2);
	}

	int query(int x, int l, int r, int idx)
	{
		if(l == r)
		{
			fix(idx);
			return !q[idx].empty() ? q[idx].top().first : 0;
		}
	
		int mid = (l + r) >> 1;
		int val = !q[idx].empty() ? q[idx].top().first : 0;

		if(x <= mid)
			chkmax(val, query(x, l, mid, 2 * idx + 1));
		else
			chkmax(val, query(x, mid + 1, r, 2 * idx + 2));
	
		return val;
	}

} L, R;

void prep_add_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) L.add_to_prep(get(l), get(mid), -l, 0, SZ(Xcord), 0);
	if(mid <= r) R.add_to_prep(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}
	
void prep_add(int y, int x, int i)
{
	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	ST[y].insert({x, i});

	prep_add_interval(bef->first, x);
	prep_add_interval(x, aft->first);
}

void prep_rem(int y, int x, int i)
{
	ST[y].erase({x, i});

	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	prep_add_interval(bef->first, aft->first);
}

void add_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) L.add(get(l), get(mid), -l, 0, SZ(Xcord), 0);
	if(mid <= r) R.add(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}

void rem_interval(int l, int r)
{
	int mid = (l + r) / 2;
	if(l <= mid) L.rem(get(l), get(mid), -l, 0, SZ(Xcord), 0);
	if(mid <= r) R.rem(get(mid + 1), get(r), r, 0, SZ(Xcord), 0);
}

int query(int x) { return max(x + L.query(get(x), 0, SZ(Xcord), 0), R.query(get(x), 0, SZ(Xcord), 0) - x); }

void add(int y, int x, int i)
{
	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	ST[y].insert({x, i});

	rem_interval(bef->first, aft->first);
	add_interval(bef->first, x);
	add_interval(x, aft->first);
}

void rem(int y, int x, int i)
{
	ST[y].erase({x, i});

	auto aft = ST[y].L_B({x, i});
	auto bef = prev(aft);

	rem_interval(bef->first, x);
	rem_interval(x, aft->first);
	add_interval(bef->first, aft->first);
}

void solve()
{
	Xcord.push_back(inf);
	Xcord.push_back(-inf);
	Xcord.push_back(0);
	Xcord.push_back(1);
	for(int i = 1; i <= k; i++)
		ST[i].insert({-inf, -1}), ST[i].insert({inf, -1});

	sort(ALL(Ev), cmp);
	for(auto it: Ev)
		if(it.type == 0) 
			prep_compr_add(it.tp, it.x, it.idx);
		else if(it.type == 1)
			prep_compr_rem(it.tp, it.x, it.idx);

	sort(ALL(Xcord));
	Xcord.erase(unique(ALL(Xcord)), Xcord.end());

	for(auto it: Ev)
		if(it.type == 0)
			prep_add(it.tp, it.x, it.idx);
		else if(it.type == 1)
			prep_rem(it.tp, it.x, it.idx);

	prep_add_interval(-inf, inf);
	L.init(0, SZ(Xcord), 0);
	R.init(0, SZ(Xcord), 0);

	for(auto it: Ev)
		if(it.type == 0)
			add(it.tp, it.x, it.idx);
		else if(it.type == 1)
			rem(it.tp, it.x, it.idx);
		else 
			answer[it.idx] = query(it.x);

	for(int i = 0; i < q; i++)
		if(answer[i] < (int)2e8) cout << answer[i] << endl;
		else cout << -1 << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20