답안 #45242 :: oj.uz

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

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	393 ms	471616 KB	Output is correct
2	Correct	358 ms	471648 KB	Output is correct
3	Correct	358 ms	471700 KB	Output is correct
4	Correct	348 ms	472160 KB	Output is correct
5	Correct	374 ms	477860 KB	Output is correct
6	Correct	379 ms	477864 KB	Output is correct
7	Correct	372 ms	478032 KB	Output is correct
8	Correct	368 ms	477920 KB	Output is correct
9	Correct	340 ms	477944 KB	Output is correct
10	Correct	345 ms	477980 KB	Output is correct
11	Correct	356 ms	478072 KB	Output is correct
12	Correct	411 ms	477920 KB	Output is correct
13	Correct	374 ms	477984 KB	Output is correct
14	Correct	459 ms	478000 KB	Output is correct
15	Correct	409 ms	474208 KB	Output is correct
16	Correct	356 ms	476796 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	393 ms	471616 KB	Output is correct
2	Correct	358 ms	471648 KB	Output is correct
3	Correct	358 ms	471700 KB	Output is correct
4	Correct	348 ms	472160 KB	Output is correct
5	Correct	374 ms	477860 KB	Output is correct
6	Correct	379 ms	477864 KB	Output is correct
7	Correct	372 ms	478032 KB	Output is correct
8	Correct	368 ms	477920 KB	Output is correct
9	Correct	340 ms	477944 KB	Output is correct
10	Correct	345 ms	477980 KB	Output is correct
11	Correct	356 ms	478072 KB	Output is correct
12	Correct	411 ms	477920 KB	Output is correct
13	Correct	374 ms	477984 KB	Output is correct
14	Correct	459 ms	478000 KB	Output is correct
15	Correct	409 ms	474208 KB	Output is correct
16	Correct	356 ms	476796 KB	Output is correct
17	Correct	370 ms	477976 KB	Output is correct
18	Correct	519 ms	477944 KB	Output is correct
19	Correct	381 ms	477920 KB	Output is correct
20	Correct	356 ms	477944 KB	Output is correct
21	Correct	421 ms	477976 KB	Output is correct
22	Correct	394 ms	478216 KB	Output is correct
23	Correct	499 ms	478056 KB	Output is correct
24	Correct	423 ms	477984 KB	Output is correct
25	Correct	388 ms	478092 KB	Output is correct
26	Correct	435 ms	478072 KB	Output is correct
27	Correct	374 ms	474644 KB	Output is correct
28	Correct	361 ms	477304 KB	Output is correct
29	Correct	390 ms	477356 KB	Output is correct

Subtask #3
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	393 ms	471616 KB	Output is correct
2	Correct	358 ms	471648 KB	Output is correct
3	Correct	358 ms	471700 KB	Output is correct
4	Correct	348 ms	472160 KB	Output is correct
5	Correct	374 ms	477860 KB	Output is correct
6	Correct	379 ms	477864 KB	Output is correct
7	Correct	372 ms	478032 KB	Output is correct
8	Correct	368 ms	477920 KB	Output is correct
9	Correct	340 ms	477944 KB	Output is correct
10	Correct	345 ms	477980 KB	Output is correct
11	Correct	356 ms	478072 KB	Output is correct
12	Correct	411 ms	477920 KB	Output is correct
13	Correct	374 ms	477984 KB	Output is correct
14	Correct	459 ms	478000 KB	Output is correct
15	Correct	409 ms	474208 KB	Output is correct
16	Correct	356 ms	476796 KB	Output is correct
17	Correct	370 ms	477976 KB	Output is correct
18	Correct	519 ms	477944 KB	Output is correct
19	Correct	381 ms	477920 KB	Output is correct
20	Correct	356 ms	477944 KB	Output is correct
21	Correct	421 ms	477976 KB	Output is correct
22	Correct	394 ms	478216 KB	Output is correct
23	Correct	499 ms	478056 KB	Output is correct
24	Correct	423 ms	477984 KB	Output is correct
25	Correct	388 ms	478092 KB	Output is correct
26	Correct	435 ms	478072 KB	Output is correct
27	Correct	374 ms	474644 KB	Output is correct
28	Correct	361 ms	477304 KB	Output is correct
29	Correct	390 ms	477356 KB	Output is correct
30	Runtime error	2715 ms	1048576 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
31	Halted	0 ms	0 KB	-

답안 #45242

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