답안 #45238 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45238	2018-04-12T05:25:57 Z	gs14004	Golf (JOI17_golf)	C++17	30 / 100	2534 ms	1048576 KB

golf

#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 = 9000000;

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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	491176 KB	Output is correct
2	Correct	378 ms	491128 KB	Output is correct
3	Correct	370 ms	491260 KB	Output is correct
4	Correct	338 ms	491832 KB	Output is correct
5	Correct	397 ms	497452 KB	Output is correct
6	Correct	477 ms	497408 KB	Output is correct
7	Correct	433 ms	497400 KB	Output is correct
8	Correct	415 ms	497484 KB	Output is correct
9	Correct	393 ms	497556 KB	Output is correct
10	Correct	398 ms	497628 KB	Output is correct
11	Correct	374 ms	497592 KB	Output is correct
12	Correct	400 ms	497656 KB	Output is correct
13	Correct	370 ms	497564 KB	Output is correct
14	Correct	375 ms	497528 KB	Output is correct
15	Correct	372 ms	493688 KB	Output is correct
16	Correct	406 ms	496312 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	491176 KB	Output is correct
2	Correct	378 ms	491128 KB	Output is correct
3	Correct	370 ms	491260 KB	Output is correct
4	Correct	338 ms	491832 KB	Output is correct
5	Correct	397 ms	497452 KB	Output is correct
6	Correct	477 ms	497408 KB	Output is correct
7	Correct	433 ms	497400 KB	Output is correct
8	Correct	415 ms	497484 KB	Output is correct
9	Correct	393 ms	497556 KB	Output is correct
10	Correct	398 ms	497628 KB	Output is correct
11	Correct	374 ms	497592 KB	Output is correct
12	Correct	400 ms	497656 KB	Output is correct
13	Correct	370 ms	497564 KB	Output is correct
14	Correct	375 ms	497528 KB	Output is correct
15	Correct	372 ms	493688 KB	Output is correct
16	Correct	406 ms	496312 KB	Output is correct
17	Correct	419 ms	497496 KB	Output is correct
18	Correct	474 ms	497528 KB	Output is correct
19	Correct	391 ms	497576 KB	Output is correct
20	Correct	366 ms	497568 KB	Output is correct
21	Correct	399 ms	497716 KB	Output is correct
22	Correct	462 ms	497632 KB	Output is correct
23	Correct	402 ms	497524 KB	Output is correct
24	Correct	407 ms	497624 KB	Output is correct
25	Correct	427 ms	497632 KB	Output is correct
26	Correct	383 ms	497732 KB	Output is correct
27	Correct	352 ms	494200 KB	Output is correct
28	Correct	396 ms	496736 KB	Output is correct
29	Correct	430 ms	496820 KB	Output is correct

Subtask #3
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	491176 KB	Output is correct
2	Correct	378 ms	491128 KB	Output is correct
3	Correct	370 ms	491260 KB	Output is correct
4	Correct	338 ms	491832 KB	Output is correct
5	Correct	397 ms	497452 KB	Output is correct
6	Correct	477 ms	497408 KB	Output is correct
7	Correct	433 ms	497400 KB	Output is correct
8	Correct	415 ms	497484 KB	Output is correct
9	Correct	393 ms	497556 KB	Output is correct
10	Correct	398 ms	497628 KB	Output is correct
11	Correct	374 ms	497592 KB	Output is correct
12	Correct	400 ms	497656 KB	Output is correct
13	Correct	370 ms	497564 KB	Output is correct
14	Correct	375 ms	497528 KB	Output is correct
15	Correct	372 ms	493688 KB	Output is correct
16	Correct	406 ms	496312 KB	Output is correct
17	Correct	419 ms	497496 KB	Output is correct
18	Correct	474 ms	497528 KB	Output is correct
19	Correct	391 ms	497576 KB	Output is correct
20	Correct	366 ms	497568 KB	Output is correct
21	Correct	399 ms	497716 KB	Output is correct
22	Correct	462 ms	497632 KB	Output is correct
23	Correct	402 ms	497524 KB	Output is correct
24	Correct	407 ms	497624 KB	Output is correct
25	Correct	427 ms	497632 KB	Output is correct
26	Correct	383 ms	497732 KB	Output is correct
27	Correct	352 ms	494200 KB	Output is correct
28	Correct	396 ms	496736 KB	Output is correct
29	Correct	430 ms	496820 KB	Output is correct
30	Runtime error	2534 ms	1048576 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #45238

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 70.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 70.0