답안 #45234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45234 2018-04-12T05:22:00 Z gs14004 Golf (JOI17_golf) C++17
0 / 100
606 ms 1048580 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 200005;
const int pool = 20000000;

vector<int> gph0[pool];
vector<int> gph1[pool];
struct node{ int l, r; }tree[pool];
int dis[pool], piv;
bool vis[pool];

void init(int s, int e, int p){
	if(s == e) return;
	tree[p].l = piv++;
	tree[p].r = piv++;
	int m = (s+e)/2;
	gph0[p].push_back(tree[p].l);
	gph0[p].push_back(tree[p].r);
	init(s, m, tree[p].l);
	init(m+1, e, tree[p].r);
}

void update(int pos, int s, int e, int prv, int cur, int v){
	if(s == e){
		if(v != -1) gph0[cur].push_back(v);
		return;
	}
	int m = (s+e)/2;
	if(pos <= m){
		tree[cur].l = piv++;
		tree[cur].r = tree[prv].r;
		gph0[cur].push_back(tree[cur].l);
		gph0[cur].push_back(tree[cur].r);
		update(pos, s, m, tree[prv].l, tree[cur].l, v);
	}
	else{
		tree[cur].l = tree[prv].l;
		tree[cur].r = piv++;
		gph0[cur].push_back(tree[cur].l);
		gph0[cur].push_back(tree[cur].r);
		update(pos, m+1, e, tree[prv].r, tree[cur].r, v);
	}
}

void query(int s, int e, int ps, int pe, int p, int v){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		gph1[v].push_back(p);
		return;
	}
	int pm = (ps+pe)/2;
	query(s, e, ps, pm, tree[p].l, v);
	query(s, e, pm+1, pe, tree[p].r, v);
}

int n, sx, sy;
pi s, e;
struct rect{ int sx, ex, sy, ey; }a[100005];
struct seg { int x, s, e, idx; };
vector<seg> segx, segy;

vector<pi> addE[MAXN];

void solve(vector<seg> l, vector<seg> r){
	for(int i=0; i<MAXN; i++) addE[i].clear();
	for(auto &i : l){
		addE[i.s].push_back(pi(i.x, i.idx));
		addE[i.e + 1].push_back(pi(i.x, -1));
	}
	int crt = piv++;
	init(0, MAXN - 1, crt);
	int ptr = 0;
	for(int i=0; i<MAXN; i++){
		for(auto &j : addE[i]){
			int nrt = piv++;
			update(j.first, 0, MAXN-1, crt, nrt, j.second);
			crt = nrt;
		}
		while(ptr < r.size() && r[ptr].x == i){
			query(r[ptr].s, r[ptr].e, 0, MAXN-1, crt, r[ptr].idx);
			ptr++;
		}
	}
}

vector<pi> ins[MAXN], del[MAXN];

vector<seg> sweep(vector<pi> &v){
	for(int i=0; i<MAXN; i++) ins[i].clear(), del[i].clear();
	for(int i=0; i<n; i++){
		if(a[i].sx + 1 < a[i].ex){
			ins[a[i].sx + 1].push_back(pi(a[i].sy, a[i].ey));
			del[a[i].ex].push_back(pi(a[i].sy, a[i].ey));
		}
	}
	set<pi> intv;
	int ptr = 0;
	vector<seg> ret;
	for(int i=0; i<MAXN; i++){
		for(auto &j : ins[i]) intv.insert(j);
		for(auto &j : del[i]) intv.erase(j);
		while(ptr < v.size() && v[ptr].first == i){
			auto l = intv.lower_bound(pi(v[ptr].second, -1));
			int re = (l == intv.end() ? (2*n+2) : l->first);
			int rs = (l == intv.begin() ? 0 : prev(l)->second);
			ret.push_back({i, rs, re, piv++});
			ptr++;
		}
	}
	return ret;
}

int main(){
	cin >> s.first >> s.second >> e.first >> e.second >> n;
	vector<int> vx = {s.first, e.first}, vy = {s.second, e.second};
	for(int i=0; i<n; i++){
		scanf("%d %d %d %d",&a[i].sx,&a[i].ex,&a[i].sy,&a[i].ey);
		vx.push_back(a[i].sx);
		vx.push_back(a[i].ex);
		vy.push_back(a[i].sy);
		vy.push_back(a[i].ey);
	}
	sort(vx.begin(), vx.end());
	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
	sort(vy.begin(), vy.end());
	vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
	auto getloc = [&](int x, vector<int> &v){
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	};
	s.first = getloc(s.first, vx);
	s.second = getloc(s.second, vy);
	e.first = getloc(e.first, vx);
	e.second = getloc(e.second, vy);
	for(int i=0; i<n; i++){
		a[i].sx = getloc(a[i].sx, vx);
		a[i].ex = getloc(a[i].ex, vx);
		a[i].sy = getloc(a[i].sy, vy);
		a[i].ey = getloc(a[i].ey, vy);
	}
	sx = vx.size();
	sy = vy.size();
	vector<pi> ptr;
	ptr.push_back(s);
	ptr.push_back(e);
	for(int i=0; i<n; i++){
		ptr.emplace_back(a[i].sx, a[i].sy);
		ptr.emplace_back(a[i].ex, a[i].ey);
	}
	ptr.emplace_back(0, 0);
	ptr.emplace_back(sx-1, sy-1);
	sort(ptr.begin(), ptr.end());
	ptr.resize(unique(ptr.begin(), ptr.end()) - ptr.begin());
	segy = sweep(ptr);
	for(int i=0; i<n; i++){
		swap(a[i].sx, a[i].sy);
		swap(a[i].ex, a[i].ey);
	}
	for(auto &i : ptr) swap(i.first, i.second);
	sort(ptr.begin(), ptr.end());
	segx = sweep(ptr);
	sort(segx.begin(), segx.end(), [&](const seg &a, const seg &b){
		return a.x < b.x;
	});
	sort(segy.begin(), segy.end(), [&](const seg &a, const seg &b){
		return a.x < b.x;
	});
	solve(segx, segy);
	solve(segy, segx);
	deque<int> que;
	memset(dis, 0x3f, sizeof(dis));
	for(auto &i : segx){
		if(i.x == s.second && i.s <= s.first && s.first <= i.e){
			dis[i.idx] = 0;
			que.push_back(i.idx);
		}
	}
	for(auto &i : segy){
		if(i.x == s.first && i.s <= s.second && s.second <= i.e){
			dis[i.idx] = 0;
			que.push_back(i.idx);
		}
	}
	while(!que.empty()){
		int x = que.front();
		que.pop_front();
		if(vis[x]) continue;
		vis[x] = 1;
		for(auto &i : gph0[x]){
			if(dis[i] > dis[x]){
				dis[i] = dis[x];
				que.push_front(i);
			}
		}
		for(auto &i : gph1[x]){
			if(dis[i] > dis[x] + 1){
				dis[i] = dis[x] + 1;
				que.push_back(i);
			}
		}
	}
	int ret = 1e9;
	for(auto &i : segx){
		if(i.x == e.second && i.s <= e.first && e.first <= i.e){
			ret = min(ret, dis[i.idx]);
		}
	}
	for(auto &i : segy){
		if(i.x == e.first && i.s <= e.second && e.second <= i.e){
			ret = min(ret, dis[i.idx]);
		}
	}
	cout << ret + 1 << endl;
}

Compilation message

golf.cpp: In function 'void solve(std::vector<seg>, std::vector<seg>)':
golf.cpp:82:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < r.size() && r[ptr].x == i){
         ~~~~^~~~~~~~~~
golf.cpp: In function 'std::vector<seg> sweep(std::vector<std::pair<int, int> >&)':
golf.cpp:105:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < v.size() && v[ptr].first == i){
         ~~~~^~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&a[i].sx,&a[i].ex,&a[i].sy,&a[i].ey);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 606 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 606 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 606 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -