답안 #45240 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45240	2018-04-12T05:32:04 Z	gs14004	Golf (JOI17_golf)	C++17	30 / 100	2516 ms	1048580 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 = 20000000;

vector<int> gph[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;
	gph[p].push_back(tree[p].l);
	gph[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) gph[cur].push_back(v);
		return;
	}
	int m = (s+e)/2;
	if(pos <= m){
		tree[cur].l = piv++;
		tree[cur].r = tree[prv].r;
		gph[cur].push_back(tree[cur].l);
		gph[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++;
		gph[cur].push_back(tree[cur].l);
		gph[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){
		gph[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 : gph[x]){
			if(i < 0 && dis[~i] > dis[x] + 1){
				dis[~i] = dis[x] + 1;
				que.push_back(~i);
			}
			if(i >= 0 && dis[i] > dis[x]){
				dis[i] = dis[x];
				que.push_front(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:81: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:104: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:119: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	410 ms	581216 KB	Output is correct
2	Correct	488 ms	581164 KB	Output is correct
3	Correct	465 ms	581288 KB	Output is correct
4	Correct	408 ms	581888 KB	Output is correct
5	Correct	481 ms	587388 KB	Output is correct
6	Correct	490 ms	587556 KB	Output is correct
7	Correct	484 ms	587480 KB	Output is correct
8	Correct	448 ms	587524 KB	Output is correct
9	Correct	459 ms	587580 KB	Output is correct
10	Correct	457 ms	587476 KB	Output is correct
11	Correct	490 ms	587576 KB	Output is correct
12	Correct	502 ms	587572 KB	Output is correct
13	Correct	493 ms	587488 KB	Output is correct
14	Correct	444 ms	587500 KB	Output is correct
15	Correct	440 ms	583740 KB	Output is correct
16	Correct	443 ms	586260 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	410 ms	581216 KB	Output is correct
2	Correct	488 ms	581164 KB	Output is correct
3	Correct	465 ms	581288 KB	Output is correct
4	Correct	408 ms	581888 KB	Output is correct
5	Correct	481 ms	587388 KB	Output is correct
6	Correct	490 ms	587556 KB	Output is correct
7	Correct	484 ms	587480 KB	Output is correct
8	Correct	448 ms	587524 KB	Output is correct
9	Correct	459 ms	587580 KB	Output is correct
10	Correct	457 ms	587476 KB	Output is correct
11	Correct	490 ms	587576 KB	Output is correct
12	Correct	502 ms	587572 KB	Output is correct
13	Correct	493 ms	587488 KB	Output is correct
14	Correct	444 ms	587500 KB	Output is correct
15	Correct	440 ms	583740 KB	Output is correct
16	Correct	443 ms	586260 KB	Output is correct
17	Correct	459 ms	587452 KB	Output is correct
18	Correct	435 ms	587536 KB	Output is correct
19	Correct	440 ms	587600 KB	Output is correct
20	Correct	687 ms	587512 KB	Output is correct
21	Correct	436 ms	587560 KB	Output is correct
22	Correct	447 ms	587652 KB	Output is correct
23	Correct	447 ms	587564 KB	Output is correct
24	Correct	498 ms	587588 KB	Output is correct
25	Correct	479 ms	587640 KB	Output is correct
26	Correct	444 ms	587616 KB	Output is correct
27	Correct	414 ms	584332 KB	Output is correct
28	Correct	422 ms	586872 KB	Output is correct
29	Correct	449 ms	587012 KB	Output is correct

Subtask #3
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	410 ms	581216 KB	Output is correct
2	Correct	488 ms	581164 KB	Output is correct
3	Correct	465 ms	581288 KB	Output is correct
4	Correct	408 ms	581888 KB	Output is correct
5	Correct	481 ms	587388 KB	Output is correct
6	Correct	490 ms	587556 KB	Output is correct
7	Correct	484 ms	587480 KB	Output is correct
8	Correct	448 ms	587524 KB	Output is correct
9	Correct	459 ms	587580 KB	Output is correct
10	Correct	457 ms	587476 KB	Output is correct
11	Correct	490 ms	587576 KB	Output is correct
12	Correct	502 ms	587572 KB	Output is correct
13	Correct	493 ms	587488 KB	Output is correct
14	Correct	444 ms	587500 KB	Output is correct
15	Correct	440 ms	583740 KB	Output is correct
16	Correct	443 ms	586260 KB	Output is correct
17	Correct	459 ms	587452 KB	Output is correct
18	Correct	435 ms	587536 KB	Output is correct
19	Correct	440 ms	587600 KB	Output is correct
20	Correct	687 ms	587512 KB	Output is correct
21	Correct	436 ms	587560 KB	Output is correct
22	Correct	447 ms	587652 KB	Output is correct
23	Correct	447 ms	587564 KB	Output is correct
24	Correct	498 ms	587588 KB	Output is correct
25	Correct	479 ms	587640 KB	Output is correct
26	Correct	444 ms	587616 KB	Output is correct
27	Correct	414 ms	584332 KB	Output is correct
28	Correct	422 ms	586872 KB	Output is correct
29	Correct	449 ms	587012 KB	Output is correct
30	Runtime error	2516 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #45240

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