제출 #252426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252426		Saboon	새 집 (APIO18_new_home)	C++14	0 / 100	5096 ms	259188 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));
	assert(it != tindex[type].end());
	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));
	assert(it != tindex[type].end());
	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(), (pre+x+1)/2) - cmp.begin();
	if (nex == -1)
		nex = m;
	else
		nex = lower_bound(cmp.begin(), cmp.end(), (nex+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(), (pre+x+1)/2) - cmp.begin();
	if (nex == -1)
		nex = m;
	else
		nex = lower_bound(cmp.begin(), cmp.end(), (nex+x+1)/2) - cmp.begin();
	change(1, 0, m, pre, nex, x, 'D');
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, k, q;
	cin >> n >> k >> q;
	vector<pair<pair<int,int>, pair<int,int>>> event;
	for (int i = 0; i < n; i++){
		int x, t, a, b;
		cin >> 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;
		cin >> 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());
	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++)
		cout << ans[i] << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'int main()':
new_home.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < event.size(); i++)
                  ~~^~~~~~~~~~~~~~

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