제출 #49549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49549		Diuven	새 집 (APIO18_new_home)	C++11	5 / 100	5035 ms	83532 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<pii> max_heap;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_heap;
const int MX=300010, inf=2e9;

struct SHOP {
	int x, type, s, e, idx;
} S[MX];

struct QUERY {
	int x, t, idx, ans;
} Q[MX];

int n, q, k;

void input(){
	cin>>n>>k>>q;
	for(int i=1; i<=n; i++){
		int t, x, s, e;
		cin>>x>>t>>s>>e;
		S[i]={x,t,s,e,i};
	}
	for(int i=1; i<=q; i++){
		int x, t;
		cin>>x>>t;
		Q[i]={x,t,i};
	}
}

void prec(){
	for(int i=1; i<=n; i++){
		S[i].x*=2;
	}
	for(int i=1; i<=q; i++){
		Q[i].x*=2;
	}
	// 좌표압축
}

//////

multiset<int> pos[MX];
int nonzero_cnt;

// seg
multiset<pii> A, B; // A가 /, B가 \

void add(int x1, int x2){
	int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
	pii p=pii(mx, my);
	A.insert(p);
	B.insert(p);
}

void del(int x1, int x2){
	int mx=(0LL+x1+x2)/2, my=(0LL+x2-x1)/2;
	pii p=pii(mx, my);
	A.erase(A.find(p));
	B.erase(B.find(p));
}

void add_store(int idx){
//	cout<<"ADD: "<<idx<<'\n';
	multiset<int> &stores = pos[S[idx].type];

	if(stores.size()==2U) nonzero_cnt++;

	int x=S[idx].x;

	if(stores.find(x)!=stores.end()){
		stores.insert(x);
		return;
	}

	auto it1=stores.lower_bound(x);
	auto it2=stores.lower_bound(x); it2--;
	int lx=*it2, rx=*it1;
	del(lx, rx);
	add(lx, x); add(x, rx);

	stores.insert(x);
}

void del_store(int idx){
//	cout<<"DEL: "<<idx<<'\n';
	multiset<int> &stores = pos[S[idx].type];

	if(stores.size()==3U) nonzero_cnt--;

	int x=S[idx].x;

	stores.erase(stores.find(x));

	if(stores.find(x)!=stores.end()){
		return;
	}

	auto it1=stores.lower_bound(x);
	auto it2=stores.lower_bound(x); it2--;
	int lx=*it2, rx=*it1;
	del(lx, x); del(x, rx);
	add(lx, rx);
}


void init(){
	// seg 초기화?
	for(int i=1; i<=k; i++){
		pos[i].insert(inf);
		pos[i].insert(-inf);
		add(-inf, inf);
	}
}

////

void debug(){
	cout<<"\nDEBUG...\n";
	for(int i=1; i<=k; i++){
		for(auto p:pos[i])
			cout<<p<<' ';
		cout<<'\n';
	}
	cout<<'\n';
}

int find(int qx){
	if(nonzero_cnt<k) return -2;
	int ans=-inf;
//	debug();
	for(pii p:A){
		int x, y; tie(x,y)=p;
		if(x<qx) continue;
		ans=max(ans, y-x+qx);
	}
	for(pii p:B){
		int x, y; tie(x,y)=p;
		if(x>qx) continue;
		ans=max(ans, y+x-qx);
	}
	return ans;
}


void solve(){
	min_heap in, out;
	for(int i=1; i<=n; i++){
		in.push({S[i].s, i});
		out.push({S[i].e, i});
	}
	sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.t<b.t; });

	init();

	for(int i=1; i<=q; i++){
		int qt=Q[i].t, qx=Q[i].x;
		while(!in.empty()){
			int t,idx; tie(t,idx)=in.top();
			if(qt<t) break;
			in.pop();
			add_store(idx);
		}
		while(!out.empty()){
			int t,idx; tie(t,idx)=out.top();
			if(qt<=t) break;
			out.pop();
			del_store(idx);
		}
		Q[i].ans=find(qx);
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	input();
	prec();
	solve();

	sort(Q+1, Q+q+1, [](QUERY &a, QUERY &b){ return a.idx<b.idx; });
	for(int i=1; i<=q; i++){
		cout<<Q[i].ans/2<<'\n';
	}
	return 0;
}

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

new_home.cpp:49:21: warning: multi-line comment [-Wcomment]
 multiset<pii> A, B; // A가 /, B가 \
                     ^

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