oj.uz

답안 #673283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673283 2022-12-20T05:47:44 Z Dan4Life 새 집 (APIO18_new_home) C++17
0 / 100
 5000 ms 124372 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long 
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using ll = long long;
const int maxn = (int)3e5+10;
const ll LINF = (ll)2e18;
struct store{
	int x, t, a, b;
};

struct query{
	int x, y, i;
};

int n, k, q;
int ans[maxn];
vector<store> v;
vector<query> Q;
vector<int> cord;
unordered_map<int,int> ind;

int32_t main(){
	cin >> n >> k >> q; v.resize(n); Q.resize(q); int cnt = 0;
	for(int i = 0; i < n; i++){
		cin >> v[i].x >> v[i].t >> v[i].a >> v[i].b;
		cord.pb(v[i].a), cord.pb(v[i].b);
	}
	for(int i = 0; i < q; i++){
		cin >> Q[i].x >> Q[i].y; Q[i].i=i;
		cord.pb(Q[i].y);
	}
	sort(all(cord)); cord.erase(unique(all(cord)),cord.end());
	for(auto u : cord) ind[u]=cnt++;
	for(auto &u : v) u.a=ind[u.a], u.b=ind[u.b];
	for(auto &u : Q) u.y=ind[u.y];
	sort(all(v), [&](store a, store b){
		if(a.a!=b.a) return a.a < b.a;
		if(a.b!=b.b) return a.b < b.b;
		if(a.x!=b.x) return a.x < b.x;
		return a.t < b.t;
	});
	sort(all(Q), [&](query a, query b){
		if(a.y!=b.y) return a.y < b.y;
		if(a.x!=b.x) return a.x < b.x;
		return a.i < b.i;
	});
	int i = 0, j = 0;
	multiset<int> S[cnt];
	set<pair<int,int>> cur;
	for(int Time = 0; Time < cnt; Time++){
		while(i < sz(v) and v[i].a==Time){
			S[v[i].t].insert(v[i].x); 
			cur.insert({v[i].b,i}); i++;
		}
		while(j < sz(Q) and Q[j].y==Time){
			for(int l = 1; l <= k; l++){
				if(S[l].empty()){ans[Q[j].i]=-1; break;}
				auto itr = S[l].lower_bound(Q[j].x);
				auto itr2 = itr; if(itr2!=S[l].begin()) itr2--;
				int dis = LINF;
				if(itr!=S[l].end()) dis = min(dis, abs(*itr-Q[j].x));
				if(itr2!=S[l].end()) dis = min(dis, abs(*itr2-Q[j].x));
				ans[Q[j].i] = max(ans[Q[j].i], dis);
			}
			j++;
		}
		while(!cur.empty()){
			auto itr = cur.begin(); int i = itr->se;
			if(itr->fi==Time){
				S[v[i].t].erase(S[v[i].t].find(v[i].x));
				cur.erase(cur.begin());
			}
			else break;
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -