Submission #113777

#	Time	Username	Problem	Language	Result	Execution time	Memory
113777		ckodser	New Home (APIO18_new_home)	C++14	47 / 100	4616 ms	109944 KiB

new_home

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 120005, INF = 2e8 + 10;
int n, k, A[N], TP[N], L[N], R[N];
int q, B[N], T[N], P[N], rev[N], res[N];
vector < int > U, S[N], E[N], Q[N];
multiset < int > ST[N];
struct SEGT
{
	multiset < int > MS[N * 2];
	inline void Add(int le, int ri, int val)
	{
		le += q; ri += q;
		for (; le < ri; le >>= 1, ri >>= 1)
		{
			if (le & 1) MS[le ++].insert(val);
			if (ri & 1) MS[-- ri].insert(val);
		}
	}
	inline void Del(multiset < int > &SS, int val)
	{
		auto it = SS.lower_bound(val);
		if ((*it) == val)
			SS.erase(it);
	}
	inline void Del(int le, int ri, int val)
	{
		le += q; ri += q;
		for (; le < ri; le >>= 1, ri >>= 1)
		{
			if (le & 1) Del(MS[le], val), le ++;
			if (ri & 1) ri --, Del(MS[ri], val);
		}
	}
	inline int Get(int i)
	{
		int Mn = INT_MAX, Mx = INT_MIN;
		for (int id = i + q; id; id >>= 1)
			if (MS[id].size())
			{
				Mn = min(Mn, *MS[id].begin());
				Mx = max(Mx, *MS[id].rbegin());
			}
		return (max(Mx - B[P[i]], B[P[i]] - Mn));
	}
};
SEGT SG;
inline bool CMP(int i, int j)
{
	return (B[i] < B[j]);
}
inline void Fix(int l, int r, int tp)
{
	B[q] = l; int le = lower_bound(P, P + q, q, CMP) - P;
	B[q] = r; int ri = upper_bound(P, P + q, q, CMP) - P;
	B[q] = (l + r) >> 1; int md = upper_bound(P, P + q, q, CMP) - P;
	if (tp == 1)
	{
		SG.Add(le, md, l);
		SG.Add(md, ri, r);
	}
	else
	{
		SG.Del(le, md, l);
		SG.Del(md, ri, r);
	}
}
int main()
{
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 0; i < n; i++)
		scanf("%d%d%d%d", &A[i], &TP[i], &L[i], &R[i]), U.pb(L[i]), U.pb(R[i] + 1);
	for (int i = 0; i < q; i++)
		scanf("%d%d", &B[i], &T[i]);

	for (int i = 0; i < 10; i++)
		U.pb(i);

	sort(U.begin(), U.end());
	U.resize(unique(U.begin(), U.end()) - U.begin());
	for (int i = 0; i < n; i++)
	{
		L[i] = (int)(lower_bound(U.begin(), U.end(), L[i]) - U.begin());
		R[i] = (int)(lower_bound(U.begin(), U.end(), R[i] + 1) - U.begin());

		S[L[i]].pb(i); E[R[i]].pb(i);
	}
	for (int i = 0; i < q; i++)
	{
		T[i] = (int)(upper_bound(U.begin(), U.end(), T[i]) - U.begin()) - 1;
		Q[T[i]].pb(i); P[i] = i;
	}
	sort(P, P + q, CMP);
	for (int i = 0; i < q; i++)
		rev[P[i]] = i;
	int bad = k;
	for (int i = 1; i <= k; i++)
	{
		ST[i].insert(-INF);
		ST[i].insert(INF);
		SG.Add(0, q, INF);
	}
	for (int i = 0; i <= (int)U.size(); i++)
	{
		for (int &id : E[i])
		{
			int tp = TP[id], l, r;
			auto it = ST[tp].lower_bound(A[id]);
			it = ST[tp].erase(it);
			r = * it; it --; l = * it;
			Fix(l, A[id], -1);
			Fix(A[id], r, -1);
			Fix(l, r, 1);
			bad += (ST[tp].size() == 2);
		}
		for (int &id : S[i])
		{
			int tp = TP[id], l, r;
			bad -= (ST[tp].size() == 2);
			auto it = ST[tp].lower_bound(A[id]);
			r = * it; it --; l = * it;
			ST[tp].insert(A[id]);
			Fix(l, r, -1);
			Fix(l, A[id], 1);
			Fix(A[id], r, 1);
		}
		for (int &id : Q[i])
		{
			if (bad)
				res[id] = -1;
			else
				res[id] = SG.Get(rev[id]);
		}
	}
	for (int i = 0; i < q; i++)
		printf("%d\n", res[i]);
	return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:72: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:74:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A[i], &TP[i], &L[i], &R[i]), U.pb(L[i]), U.pb(R[i] + 1);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
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", &B[i], &T[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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