oj.uz

답안 #49548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49548 2018-05-31T06:02:01 Z Diuven 새 집 (APIO18_new_home) C++11
0 / 100
 5000 ms 83332 KB 
#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];

// 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';
	// 지금 샵 : S[idx];
	// 지금 셋 : pos[S[idx].type]
	multiset<int> &stores = pos[S[idx].type];

	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];

	int x=S[idx].x;

	if(stores.find(x)==stores.end()){
		return;
	}
	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){
	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

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 13 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 13 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5052 ms 83332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5027 ms 83332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 13 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14456 KB Output is correct
2 Incorrect 13 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -