Submission #111238

#	Time	Username	Problem	Language	Result	Execution time	Memory
111238		diamond_duke	New Home (APIO18_new_home)	C++11	57 / 100	5043 ms	190540 KiB

new_home

#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
constexpr int INF = 2e8 + 5;
int seg[20000005], lson[20000005], rson[20000005], t_cnt;
void modify(int &u, int l, int r, int pos, int val)
{
	if (!u)
		u = ++t_cnt;
	if (l == r)
	{
		seg[u] = val;
		return;
	}
	int m = l + r >> 1;
	if (pos <= m)
		modify(lson[u], l, m, pos, val);
	else
		modify(rson[u], m + 1, r, pos, val);
	seg[u] = std::min(seg[lson[u]], seg[rson[u]]);
}
int query(int u, int l, int r, int pos, int mn)
{
	if (l == r)
		return l;
	int m = l + r >> 1;
	if (m >= pos && std::min(mn, seg[rson[u]]) >= pos - (m - pos))
		return query(lson[u], l, m, pos, std::min(mn, seg[rson[u]]));
	return query(rson[u], m + 1, r, pos, mn);
}
struct { int pos, tp, l, r; } shop[300005];
int app[600005], ans[300005], rt;
std::multiset<int> all[300005];
std::map<int, std::multiset<int> > pre;
std::vector<int> vec[600005];
std::vector<std::pair<int, int> > qry[600005];
void add_pre(int x, int y)
{
	auto &se = pre[x];
	se.insert(y);
	modify(rt, 0, INF, x, *se.begin());
}
void del_pre(int x, int y)
{
	auto &se = pre[x];
	se.erase(se.find(y));
	modify(rt, 0, INF, x, se.empty() ? INF : *se.begin());
}
int main()
{
	// freopen("uoj-414.in", "r", stdin);
	seg[0] = INF;
	int n, k, q, cnt = 0;
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d%d%d", &shop[i].pos, &shop[i].tp, &shop[i].l, &shop[i].r);
		app[cnt++] = shop[i].l;
		app[cnt++] = shop[i].r + 1;
		shop[i].tp--;
	}
	std::sort(app, app + cnt);
	cnt = std::unique(app, app + cnt) - app;
	for (int i = 0; i < n; i++)
	{
		int l = std::lower_bound(app, app + cnt, shop[i].l) - app;
		int r = std::lower_bound(app, app + cnt, shop[i].r + 1) - app;
		vec[l].push_back(i);
		vec[r].push_back(~i);
	}
	for (int i = 0; i < q; i++)
	{
		int pos, t;
		scanf("%d%d", &pos, &t);
		t = std::upper_bound(app, app + cnt, t) - app - 1;
		if (t < 0)
			ans[i] = -1;
		else
			qry[t].emplace_back(pos, i);
	}
	for (int i = 0; i < k; i++)
	{
		add_pre(INF, -INF);
		all[i] = {INF};
	}
	for (int i = 0; i < cnt; i++)
	{
		for (int u : vec[i])
		{
			int x = -INF, y = INF;
			auto get_adj = [&] (std::multiset<int> &se, int pos)
			{
				auto it = se.lower_bound(pos);
				if (it != se.end())
					y = *it;
				if (it != se.begin())
					x = *--it;
			};
			if (u >= 0)
			{
				int pos = shop[u].pos;
				auto &se = all[shop[u].tp];
				get_adj(se, pos);
				se.insert(pos);
				del_pre(y, x);
				add_pre(y, pos);
				add_pre(pos, x);
			}
			else
			{
				u = ~u;
				int pos = shop[u].pos;
				auto &se = all[shop[u].tp];
				se.erase(se.find(pos));
				get_adj(se, pos);
				del_pre(y, pos);
				del_pre(pos, x);
				add_pre(y, x);
			}
		}
		for (auto &it : qry[i])
		{
			int idx = it.second, pos = it.first;
			ans[idx] = query(rt, 0, INF, pos, INF);
			if (ans[idx] == INF)
				ans[idx] = -1;
			else
				ans[idx] -= pos;
		}
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void modify(int&, int, int, int, int)':
new_home.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
new_home.cpp: In function 'int query(int, int, int, int, int)':
new_home.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l + r >> 1;
          ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:56: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &shop[i].pos, &shop[i].tp, &shop[i].l, &shop[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &pos, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~

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