Submission #367977

#	Time	Username	Problem	Language	Result	Execution time	Memory
367977		arnold518	New Home (APIO18_new_home)	C++14	47 / 100	5108 ms	304240 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 = 1e6;
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<int> comp;

int ans[MAXN+10];

struct SEG
{
	multiset<int, greater<int>> val[MAXN+10];
	int tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		tree[node]=-INF;
		if(tl==tr) return;
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
	}
	void update(int node, int tl, int tr, int p)
	{
		if(tl==tr)
		{
			if(!val[tl].empty()) tree[node]=*val[tl].begin();
			else tree[node]=-INF;
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p);
		else update(node*2+1, mid+1, tr, p);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return -INF;
		int mid=tl+tr>>1;
		return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
	void push(int x, int y)
	{
		val[x].insert(y);
		update(1, 1, comp.size(), x);
	}
	void pop(int x, int y)
	{
		assert(val[x].find(y)!=val[x].end());
		val[x].erase(val[x].find(y));
		update(1, 1, comp.size(), x);
	}
	int query(int l, int r)
	{
		return query(1, 1, comp.size(), l, r);
	}
}seg1, seg2;

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

void pop(int x, int y)
{
	int x2=lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
	assert(comp[x2-1]==x);
	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);

	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);
			comp.push_back((now.x+r)>>1);
			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);
			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);
	}

	seg1.init(1, 1, comp.size());
	seg2.init(1, 1, comp.size());

	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);
			push((l+now.x)/2, (now.x-l)/2);
			push((now.x+r)/2, (r-now.x)/2);

			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);
			pop((l+now.x)/2, (now.x-l)/2);
			pop((now.x+r)/2, (r-now.x)/2);

			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(), now.l)-comp.begin()+1;
			val=max(val, seg1.query(x, comp.size())+now.l);
			x=upper_bound(comp.begin(), comp.end(), now.l)-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 member function 'void SEG::init(int, int, int)':
new_home.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid=tl+tr>>1;
      |           ~~^~~
new_home.cpp: In member function 'void SEG::update(int, int, int, int)':
new_home.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid=tl+tr>>1;
      |           ~~^~~
new_home.cpp: In member function 'int SEG::query(int, int, int, int, int)':
new_home.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int mid=tl+tr>>1;
      |           ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |  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]
  107 |   scanf("%d%d%d%d", &A[i].x, &A[i].t, &A[i].a, &A[i].b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |   scanf("%d%d", &B[i].l, &B[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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