oj.uz

Submission #33842

# Submission time Handle Problem Language Result Execution time Memory
33842 2017-11-03T04:30:17 Z cprayer 개구리 (KOI13_frog) C++14
0 / 22
 439 ms 8028 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long long unsigned llu;
typedef long double ld;

const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 1e5 + 9;

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

point arr[MAX_N];
int f[MAX_N];
int N, r, d;

int find(int v){
	return f[v] == v ? v : f[v] = find(f[v]);
}

void merge(int u, int v){
	u = find(u);
	v = find(v);
	if(u == v) return;
	if(u > v) swap(u, v);
	f[v] = u;
}

void visit(int type){
	if(type){
		for(int i = 0; i < N; i++) swap(arr[i].x, arr[i].y);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqmin;
	map<int, int> curr;
	set<pair<int, int>> cand;
	for(int i = 0; i < N; i++){
		while(!pqmin.empty() && pqmin.top().first + r + d < arr[i].x){
			int p = pqmin.top().second;
			if(curr[arr[p].y] == 1){
				cand.erase({arr[p].y, p});
				curr[arr[p].y]--;
			}
			pqmin.pop();
		}
		auto it = cand.lower_bound({arr[i].y - r, -inf});
		if(it != cand.end()){
			if(it->first <= arr[i].y + r) merge(it->second, i);
		}
		pqmin.push({arr[i].x, arr[i].i});
		if(!curr[arr[i].y]) cand.insert({arr[i].y, arr[i].i});
		curr[arr[i].y]++;
	}
	while(!pqmin.empty()) pqmin.pop();
	curr.clear();
	cand.clear();
	priority_queue<pair<int, int>> pqmax;
	for(int i = N - 1; i >= 0; i--){
		while(!pqmax.empty() && arr[i].x + r + d < pqmax.top().first){
			int p = pqmax.top().second;
			if(curr[arr[p].y] == 1){
				cand.erase({arr[p].y, p});
				curr[arr[p].y]--;
			}
			pqmax.pop();
		}
		auto it = cand.lower_bound({arr[i].y - r, -inf});
		if(it != cand.end()){
			if(it->first <= arr[i].y + r) merge(it->second, i);
		}
		pqmax.push({arr[i].x, arr[i].i});
		if(!curr[arr[i].y]) cand.insert({arr[i].y, arr[i].i});
		curr[arr[i].y]++;
	}
	while(!pqmax.empty()) pqmax.pop();
	curr.clear();
	cand.clear();
	if(type){
		for(int i = 0; i < N; i++) swap(arr[i].x, arr[i].y);
	}
}

int main(){
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cout.sync_with_stdio(false);
	cin >> N >> r;
	for(int i = 0; i < N; i++){
		int x, y;
		cin >> x >> y;
		arr[i] = {x, y, i};
	}
	for(int i = 0; i < N; i++) f[i] = i;
	cin >> d;
	sort(arr, arr + N, [](point &a, point &b){
		if(a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});
	visit(0);
	sort(arr, arr + N, [](point &a, point &b){
		if(a.y != b.y) return a.y < b.y;
		return a.x < b.x;
	});
	visit(1);
	ll ans = 0;
	for(int i = 0; i < N; i++){
		if(find(arr[i].i) == 0) ans = max(ans, 1LL * arr[i].x + arr[i].y + 2 * r);
	}
	printf("%lld", ans);
	return 0;
}

Subtask #1
0 / 1.98

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

Subtask #2
0 / 2.64

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

Subtask #3
0 / 3.52

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

Subtask #4
0 / 4.18

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

Subtask #5
0 / 4.62

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

Subtask #6
0 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 196 ms 5992 KB Output is correct
2 Incorrect 439 ms 8028 KB Output isn't correct
3 Halted 0 ms 0 KB -