oj.uz

Submission #49358

# Submission time Handle Problem Language Result Execution time Memory
49358 2018-05-27T13:34:58 Z 노영훈(#1273, Diuven) New Home (APIO18_new_home) C++
0 / 100
 435 ms 28396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii>> min_heap;
const int MX=300010, inf=2e9;

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

struct node {
	int x, p, s, e;
} D[MX];

vector<node> S[MX];

vector<int> T;

int n, q, k;

void init(){
	cin>>n>>k>>q;
	for(int i=1; i<=n; i++){
		int x,p,s,e;
		cin>>x>>p>>s>>e;
		D[i]={x,p,s,e};
		S[p].push_back({x,p,s,e});
		T.push_back(s);
		T.push_back(e);
	}
	for(int i=1; i<=q; i++){
		int t,x;
		cin>>x>>t;
		Q[i]={t,x,i};
		T.push_back(t);
	}
	sort(T.begin(), T.end());
	T.resize(unique(T.begin(), T.end())-T.begin());
}

void solve1(){
	multiset<int> ms[410];
	min_heap in, out, qes;
	for(int i=1; i<=n; i++)
		in.push({D[i].s, i}), out.push({D[i].e, i});
	for(int i=1; i<=q; i++)
		qes.push({Q[i].t, i});
	while(!qes.empty()){
		int qt, qidx; tie(qt,qidx)=qes.top();
		while(!in.empty()){
			int t, idx; tie(t,idx)=in.top();
			if(t>qt) break;
			in.pop();
			ms[D[idx].p].insert(D[idx].x);
		}
		while(!out.empty()){
			int t, idx; tie(t,idx)=out.top();
			if(t>=qt) break;
			out.pop();
			ms[D[idx].p].erase(ms[D[idx].p].find(D[idx].x));
		}
		int &ans=Q[qidx].ans, qx=Q[qidx].x;
		for(int i=1; i<=k; i++){
			if(ms[i].empty()) ans=inf;
			auto it1=ms[i].lower_bound(qx);
			auto it2=ms[i].lower_bound(qx);
			int ux=qx, dx=qx;
			if(it1!=ms[i].end()) ux=*it1;
			if(it1!=ms[i].begin()){
				it2--;
				dx=*it2;
			}
			ans=max({ans, abs(ux-qx), abs(dx-qx)});
		}
		if(ans==inf) ans=-1;
		qes.pop();
	}
	for(int i=1; i<=q; i++)
		cout<<Q[i].ans<<'\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	init();
	if(k<=400){
		solve1();
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 8 ms 7520 KB Output is correct
4 Incorrect 8 ms 7520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 8 ms 7520 KB Output is correct
4 Incorrect 8 ms 7520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 383 ms 28396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 28396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 8 ms 7520 KB Output is correct
4 Incorrect 8 ms 7520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7520 KB Output is correct
3 Correct 8 ms 7520 KB Output is correct
4 Incorrect 8 ms 7520 KB Output isn't correct
5 Halted 0 ms 0 KB -