Submission #49547

#	Time	Username	Problem	Language	Result	Execution time	Memory
49547		Diuven	New Home (APIO18_new_home)	C++11	0 / 100	5024 ms	83336 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=1e9;

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;
	}
	// 좌표 2배, 좌표압축, 압축후 다시 찾을 수 있도록 세팅
	// 좌표압축: 어떻게하지??
	// +- 무한 포함해서.
}

//////

multiset<int> pos[MX];

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

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

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

void add_store(int idx){
	// 지금 샵 : S[idx];
	// 지금 셋 : pos[S[idx].type]
	multiset<int> &stores = pos[S[idx].type];

	int x=S[idx].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, rx);
	add(lx, x); add(x, rx);

	stores.insert(x);
}

void del_store(int idx){
	multiset<int> &stores = pos[S[idx].type];

	int x=S[idx].x;

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

	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';
	}
}

int find(int qx){
	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+n+1, [](QUERY &a, QUERY &b){ return a.idx<b.idx; });
	for(int i=1; i<=q; i++){
		cout<<(Q[i].ans>inf/3 ? -1 : Q[i].ans/2)<<'\n';
	}
	return 0;
}

Compilation message (stderr)

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

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