Submission #172063

#	Time	Username	Problem	Language	Result	Execution time	Memory
172063		AngusRitossa	New Home (APIO18_new_home)	C++14	47 / 100	4804 ms	482152 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define MXN 60010
#define MXNODES MXN*80
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
set<pair<int, int> > segments[MXNODES];
int l[MXNODES], r[MXNODES], upto;
void addsegment(int s, int e, pair<int, int> val, int curr = 1, int cstart = 0, int cend = 1e8)
{
	if (e < cstart || s > cend) return;
	if (s <= cstart && cend <= e)
	{
		segments[curr].insert(val);
		return;
	}
	int mid = (cstart+cend)/2;
	if (e <= mid) 
	{
		if (!l[curr]) l[curr] = ++upto;
		addsegment(s, e, val, l[curr], cstart, mid);
	}
	else if (s > mid)
	{
		if (!r[curr]) r[curr] = ++upto;
		addsegment(s, e, val, r[curr], mid+1, cend);
	}
	else
	{
		if (!l[curr]) l[curr] = ++upto;
		if (!r[curr]) r[curr] = ++upto;
		addsegment(s, e, val, l[curr], cstart, mid);
		addsegment(s, e, val, r[curr], mid+1, cend);
	}
}
void removesegment(int s, int e, pair<int, int> val, int curr = 1, int cstart = 0, int cend = 1e8)
{
	if (e < cstart || s > cend) return;
	if (s <= cstart && cend <= e)
	{
		segments[curr].erase(val);
		return;
	}
	int mid = (cstart+cend)/2;
	if (e <= mid) 
	{
		removesegment(s, e, val, l[curr], cstart, mid);
	}
	else if (s > mid)
	{
		removesegment(s, e, val, r[curr], mid+1, cend);
	}
	else
	{
		removesegment(s, e, val, l[curr], cstart, mid);
		removesegment(s, e, val, r[curr], mid+1, cend);
	}
}
pair<int, int> query(int node, int curr = 1, int cstart = 0, int cend = 1e8)
{
	pair<int, int> ans = { 2e8, -2e8 };
	if (segments[curr].size()) ans.first = segments[curr].begin()->first, ans.second = segments[curr].rbegin()->first;
	if (cstart == cend) return ans;
	int mid = (cstart+cend)/2;
	pair<int, int> child;
	if (node <= mid) child = query(node, l[curr], cstart, mid);
	else child = query(node, r[curr], mid+1, cend);
	ans.first = min(ans.first, child.first);
	ans.second = max(ans.second, child.second);
	return ans;
}
int n, k, q, x[MXN], t[MXN], a[MXN], b[MXN], amwithshop;
vector<pair<int, int> > events;
set<pair<int, int> > shops[MXN]; 
pair<int, int> queries[MXN];
int sq[MXN], ans[MXN];
int doQuery(int loc)
{
	if (amwithshop != k)
	{
		return -1;
	}
	// jdi
	auto res = query(loc);
	D("%d %d\n", res.first, res.second);
	int before = loc-res.first;
	int after = res.second-loc;
	int ans = max(before, after);
	return ans;
}
int main()
{
	++upto;
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 1; i <= k; i++) 
	{
		shops[i].insert({ -2e8, -1 }), shops[i].insert({ 2e8, -2 });
		// dumbie stuff
		addsegment(-2e8, 0, {-2e8, -1}, 0);
		addsegment(0, 2e8, {2e8, -2}, 1);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
		events.emplace_back(i, 0);
		events.emplace_back(i, 1);
	}
	for (int i = 0; i < q; i++)
	{
		scanf("%d%d", &queries[i].second, &queries[i].first);
	}
	iota(sq, sq+q, 0);
	sort(sq, sq+q, [&](int a, int b) { return queries[a].first < queries[b].first;});
	int qupto = 0;

	sort(events.begin(), events.end(), [](const pair<int, int> &i, const pair<int, int> &j)
	{
		int val1 = i.second ? b[i.first] : a[i.first];
		int val2 = j.second ? b[j.first] : a[j.first];
		return make_pair(val1, i.second) < make_pair(val2, j.second);
	});
	for (auto f : events)
	{
		int i = f.first;
		int eventType = f.second;
		int timeOfEvent = eventType ? b[i]+1 : a[i];
		while (qupto < q && queries[sq[qupto]].first < timeOfEvent)
		{
			// do query
			ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
			qupto++;
		}
		D("\nprocessing %d %d : %d (time: %d)\n", i, eventType, t[i], eventType ? b[i] : a[i]);
		if (!eventType) // new thing
		{
			D("new thing\n");
			if (shops[t[i]].size() == 2) amwithshop++;
			auto it = shops[t[i]].lower_bound({x[i], i});
			auto after = *it;
			auto before = *prev(it);
			// remove the ranges 
			int mid = (before.first+after.first)/2;
			removesegment(before.first, mid, before);
			mid = (before.first+after.first+1)/2;
			removesegment(mid, after.first, after);
			// add in, then add ranges (4)
			shops[t[i]].insert({x[i], i});
			mid = (before.first+x[i])/2;
			D("adding range first %d %d\n", before.first, mid);
			addsegment(before.first, mid, before);
			mid = (before.first+x[i]+1)/2;
			D("adding range second %d %d\n", mid, x[i]);
			addsegment(mid, x[i], { x[i], i });
			mid = (x[i]+after.first)/2;
			D("adding range first %d %d\n", x[i], mid);
			addsegment(x[i], mid, { x[i], i });
			mid = (x[i]+after.first+1)/2;
			D("adding range second %d %d\n", mid, after.first);
			addsegment(mid, after.first, after);
		}
		else // end of thing
		{
			D("end of thing\n");
			shops[t[i]].erase({x[i], i});
			auto it = shops[t[i]].lower_bound({x[i], i});
			auto after = *it;
			auto before = *prev(it);
			// remove ranges
			int mid = (before.first+x[i])/2;
			removesegment(before.first, mid, before);
			mid = (before.first+x[i]+1)/2;
			removesegment(mid, x[i], { x[i], i });
			mid = (x[i]+after.first)/2;
			removesegment(x[i], mid, { x[i], i });
			mid = (x[i]+after.first+1)/2;
			removesegment(mid, after.first, after);

			// add new ranges
			mid = (before.first+after.first)/2;
			addsegment(before.first, mid, before);
			mid = (before.first+after.first+1)/2;
			addsegment(mid, after.first, after);
			if (shops[t[i]].size() == 2) amwithshop--;
		}
	}
	while (qupto < q)
	{
		ans[sq[qupto]] = doQuery(queries[sq[qupto]].second);
		qupto++;
	}
	for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &queries[i].second, &queries[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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