Submission #367978

#	Time	Username	Problem	Language	Result	Execution time	Memory
367978		arnold518	New Home (APIO18_new_home)	C++14	100 / 100	4456 ms	176076 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int SEGN = 1048576;
const int INF = 2e8;

int N, Q, K;

struct Data
{
	int x, t, a, b;
};

struct Query
{
	int l, y, p;
};

struct Data2
{
	int t, p, q;
};

Data A[MAXN+10];
Query B[MAXN+10];

set<int> S[MAXN+10];
multiset<int> S2[MAXN+10];
vector<pii> comp;

int ans[MAXN+10];

struct SEG
{
	int tree[SEGN*2+10];
	void init()
	{
		for(int i=0; i<SEGN*2+10; i++) tree[i]=-INF;
	}
	void update(int p, int q)
	{
		p+=SEGN;
		tree[p]=q;
		for(int node=p>>1; node>=1; node>>=1) tree[node]=max(tree[node<<1], tree[node<<1|1]);
	}
	int query(int l, int r)
	{
		l+=SEGN; r+=SEGN; r++;
		int ret=-INF;
		for(; l<r; l>>=1, r>>=1)
		{
			if(l&1) ret=max(ret, tree[l++]);
			if(r&1) ret=max(ret, tree[--r]);
		}
		return ret;
	}
	void push(int x, int y)
	{
		update(x, y);
	}
	void pop(int x, int y)
	{
		update(x, -INF);
	}
}seg1, seg2;

void push(int x, int y, int k)
{
	int x2=lower_bound(comp.begin(), comp.end(), pii(x, k))-comp.begin()+1;
	seg1.push(x2, y-x);
	seg2.push(x2, x+y);
}

void pop(int x, int y, int k)
{
	int x2=lower_bound(comp.begin(), comp.end(), pii(x, k))-comp.begin()+1;
	seg1.pop(x2, y-x);
	seg2.pop(x2, x+y);
}

int main()
{
	scanf("%d%d%d", &N, &K, &Q);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d%d%d", &A[i].x, &A[i].t, &A[i].a, &A[i].b);
		A[i].x*=2;
	}
	for(int i=1; i<=Q; i++)
	{
		scanf("%d%d", &B[i].l, &B[i].y);
		B[i].l*=2;
		B[i].p=i;
	}

	vector<Data2> V;
	for(int i=1; i<=N; i++)
	{
		V.push_back({A[i].a, -1, i});
		V.push_back({A[i].b, 1, i});
	}
	for(int i=1; i<=Q; i++)
	{
		V.push_back({B[i].y, 0, i});
	}

	sort(V.begin(), V.end(), [&](const Data2 &p, const Data2 &q)
	{
		if(p.t!=q.t) return p.t<q.t;
		return p.p<q.p;
	});

	for(int i=1; i<=K; i++)
	{
		S[i].insert(-INF);
		S[i].insert(INF*2);
		S2[i].insert(-INF);
		S2[i].insert(INF*2);
		comp.push_back({INF/2, i});
	}

	for(auto it : V)
	{
		if(it.p<0)
		{
			auto now = A[it.q];
			S2[now.t].insert(now.x);
			if(S[now.t].find(now.x)!=S[now.t].end()) continue;

			auto pt=S[now.t].lower_bound(now.x);
			int l=*prev(pt), r=*pt;
			comp.push_back({(l+now.x)>>1, now.t});
			comp.push_back({(now.x+r)>>1, now.t});
			S[now.t].insert(now.x);
		}
		else if(it.p>0)
		{
			auto now = A[it.q];
			S2[now.t].erase(S2[now.t].find(now.x));
			if(S2[now.t].find(now.x)!=S2[now.t].end()) continue;

			auto pt=S[now.t].lower_bound(now.x);
			int l=*prev(pt), r=*next(pt);
			comp.push_back({(l+r)>>1, now.t});
			S[now.t].erase(now.x);
		}
	}

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());

	for(int i=1; i<=K; i++)
	{
		S[i].clear(); S2[i].clear();
		S[i].insert(-INF);
		S[i].insert(INF*2);
		S2[i].insert(-INF);
		S2[i].insert(INF*2);
		push(INF/2, INF+INF/2, i);
	}

	seg1.init();
	seg2.init();

	int cnt=0;
	for(auto it : V)
	{
		if(it.p<0)
		{
			auto now = A[it.q];
			if(S2[now.t].size()==2) cnt++;
			S2[now.t].insert(now.x);
			if(S[now.t].find(now.x)!=S[now.t].end()) continue;

			auto pt=S[now.t].lower_bound(now.x);
			int l=*prev(pt), r=*pt;

			pop((l+r)/2, (r-l)/2, now.t);
			push((l+now.x)/2, (now.x-l)/2, now.t);
			push((now.x+r)/2, (r-now.x)/2, now.t);

			S[now.t].insert(now.x);
		}
		else if(it.p>0)
		{
			auto now = A[it.q];
			S2[now.t].erase(S2[now.t].find(now.x));
			if(S2[now.t].size()==2) cnt--;
			if(S2[now.t].find(now.x)!=S2[now.t].end()) continue;

			auto pt=S[now.t].lower_bound(now.x);
			int l=*prev(pt), r=*next(pt);

			push((l+r)/2, (r-l)/2, now.t);
			pop((l+now.x)/2, (now.x-l)/2, now.t);
			pop((now.x+r)/2, (r-now.x)/2, now.t);

			S[now.t].erase(now.x);
		}
		else
		{
			auto now = B[it.q];
			if(cnt!=K)
			{
				ans[it.q]=-1;
				continue;
			}
			int val=-INF;
			int x=lower_bound(comp.begin(), comp.end(), pii(now.l, 0))-comp.begin()+1;
			val=max(val, seg1.query(x, comp.size())+now.l);
			x=upper_bound(comp.begin(), comp.end(), pii(now.l, INF))-comp.begin();
			val=max(val, seg2.query(1, x)-now.l);
			ans[it.q]=val/2;
		}	
	}
	for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d%d%d", &N, &K, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |   scanf("%d%d%d%d", &A[i].x, &A[i].t, &A[i].a, &A[i].b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d", &B[i].l, &B[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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