Submission #252437

#	Time	Username	Problem	Language	Result	Execution time	Memory
252437		Saboon	New Home (APIO18_new_home)	C++14	47 / 100	5110 ms	312252 KiB

new_home

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 20;
const int inf = 1e9;

set<pair<int,int>> tindex[maxn];
int ans[maxn];
vector<int> cmp;
multiset<int> seg[8*maxn];

pair<int,int> get(int id, int L, int R, int idx){
	if (R <= idx or idx < L)
		return {inf, 0};
	if (L + 1 == R){
		if (seg[id].empty())
			return {inf,0};
		return {*seg[id].begin(), *seg[id].rbegin()};
	}
	pair<int,int> ret = {inf,0};
	if (!seg[id].empty())
		ret = {*seg[id].begin(), *seg[id].rbegin()};
	int mid = (L + R) >> 1;
	auto it1 = get(2*id+0, L, mid, idx);
	auto it2 = get(2*id+1, mid, R, idx);
	ret.first = min({ret.first, it1.first, it2.first});
	ret.second = max({ret.second, it1.second, it2.second});
	return ret;
}

void change(int id, int L, int R, int l, int r, int x, char type){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		if (type == 'A')
			seg[id].insert(x);
		else
			seg[id].erase(seg[id].find(x));
		return;
	}
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, l, r, x, type);
	change(2*id+1, mid, R, l, r, x, type);
}

int m;

pair<int,int> getpre(int x, int idx, int type){
	auto it = tindex[type].lower_bound(make_pair(x,idx));
	if (it == tindex[type].begin())
		return {-1,-1};
	it --;
	return *it;
}

pair<int,int> getnex(int x, int idx, int type){
	auto it = tindex[type].lower_bound(make_pair(x,idx));
	it ++;
	if (it == tindex[type].end())
		return {-1,-1};
	return *it;
}

void add(int x, int idx, int type){
	if (x == -1)
		return;
	int pre = getpre(x,idx,type).first, nex = getnex(x,idx,type).first;
	if (pre == -1)
		pre = 0;
	else
		pre = lower_bound(cmp.begin(), cmp.end(), (cmp[pre]+cmp[x]+1)/2) - cmp.begin();
	if (nex == -1)
		nex = m;
	else
		nex = lower_bound(cmp.begin(), cmp.end(), (cmp[nex]+cmp[x]+1)/2) - cmp.begin();
	change(1, 0, m, pre, nex, x, 'A');
}

void del(int x, int idx, int type){
	if (x == -1)
		return;
	int pre = getpre(x,idx,type).first, nex = getnex(x,idx,type).first;
	if (pre == -1)
		pre = 0;
	else
		pre = lower_bound(cmp.begin(), cmp.end(), (cmp[pre]+cmp[x]+1)/2) - cmp.begin();
	if (nex == -1)
		nex = m;
	else
		nex = lower_bound(cmp.begin(), cmp.end(), (cmp[nex]+cmp[x]+1)/2) - cmp.begin();
	change(1, 0, m, pre, nex, x, 'D');
}

int main(){
	int n, k, q;
	scanf("%d%d%d", &n, &k, &q);
	vector<pair<pair<int,int>, pair<int,int>>> event;
	for (int i = 0; i < n; i++){
		int x, t, a, b;
		scanf("%d%d%d%d", &x, &t, &a, &b);
		event.push_back({{a,i}, {x,t}}); 
		event.push_back({{b,n+1+i}, {x,t}});
		cmp.push_back(x);
	}
	for (int i = 0; i < q; i++){
		int l, y;
		scanf("%d%d", &l, &y);
		cmp.push_back(l);
		event.push_back({{y,n}, {l,i}});
	}
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	m = cmp.size();
	for (int i = 0; i < event.size(); i++)
		event[i].second.first = lower_bound(cmp.begin(), cmp.end(), event[i].second.first) - cmp.begin();
	sort(event.begin(), event.end());
	if (n <= 60000 and q <= 60000){
		int cnt = 0;
		for (auto Q : event){
			if (Q.first.second < n){
				int x = Q.second.first, type = Q.second.second, idx = Q.first.second;
				if (tindex[type].empty())
					cnt ++;
				tindex[type].insert({x,idx});
				auto nex = getnex(x, idx, type), pre = getpre(x, idx, type);
				tindex[type].erase({x,idx});
				del(pre.first, pre.second, type);
				del(nex.first, nex.second, type);
				tindex[type].insert({x,idx});
				add(x, idx, type);
				add(pre.first, pre.second, type);
				add(nex.first, nex.second, type);
			}
			else if (Q.first.second > n){
				int x = Q.second.first, type = Q.second.second, idx = Q.first.second - n - 1;
				auto nex = getnex(x,idx,type), pre = getpre(x,idx,type);
				del(x, idx, type);
				del(pre.first, pre.second, type);
				del(nex.first, nex.second, type);
				tindex[type].erase({x,idx});
				if (tindex[type].empty())
					cnt --;
				add(pre.first, pre.second, type);
				add(nex.first, nex.second, type);
			}
			else{
				int x = Q.second.first, idx = Q.second.second;
				if (cnt < k){
					ans[idx] = -1;
					continue;
				}
				auto it = get(1, 0, m, x);
				ans[idx] = max(cmp[x]-cmp[it.first], cmp[it.second]-cmp[x]);
			}
		}
		for (int i = 0; i < q; i++)
			printf("%d\n", ans[i]);
		return 0;
	}
	int cnt = 0;
	for (auto Q : event){
		if (Q.first.second < n){
			int x = Q.second.first, type = Q.second.second, idx = Q.first.second;
			if (tindex[type].empty())
				cnt ++;
			tindex[type].insert({x,idx});
		}
	}
	memset(ans, -1, sizeof ans);
	if (cnt == k){
		for (int t = 1; t <= k; t++)
			for (auto [x,idx] : tindex[t])
				add(t,idx,t);
		for (auto Q : event){
			if (Q.first.second > n){
				int x = Q.second.first, type = Q.second.second, idx = Q.first.second - n - 1;
				auto nex = getnex(x,idx,type), pre = getpre(x,idx,type);
				del(x, idx, type);
				del(pre.first, pre.second, type);
				del(nex.first, nex.second, type);
				tindex[type].erase({x,idx});
				if (tindex[type].empty())
					cnt --;
				add(pre.first, pre.second, type);
				add(nex.first, nex.second, type);
			}
			else if (Q.first.second == n){
				int x = Q.second.first, idx = Q.second.second;
				if (cnt < k){
					ans[idx] = -1;
					continue;
				}
				auto it = get(1, 0, m, x);
				ans[idx] = max(cmp[x]-cmp[it.first], cmp[it.second]-cmp[x]);
			}
		}
	}
	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:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < event.size(); i++)
                  ~~^~~~~~~~~~~~~~
new_home.cpp:172:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for (auto [x,idx] : tindex[t])
              ^
new_home.cpp:172:20: warning: unused variable 'x' [-Wunused-variable]
    for (auto [x,idx] : tindex[t])
                    ^
new_home.cpp:96: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:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x, &t, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", &l, &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