oj.uz

답안 #45237

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

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 528 ms 643784 KB Output is correct
2 Correct 516 ms 643808 KB Output is correct
3 Correct 465 ms 644024 KB Output is correct
4 Correct 446 ms 644476 KB Output is correct
5 Correct 462 ms 650080 KB Output is correct
6 Correct 451 ms 650080 KB Output is correct
7 Correct 475 ms 649988 KB Output is correct
8 Correct 467 ms 650080 KB Output is correct
9 Correct 504 ms 650104 KB Output is correct
10 Correct 568 ms 650188 KB Output is correct
11 Correct 458 ms 650208 KB Output is correct
12 Correct 565 ms 650120 KB Output is correct
13 Correct 552 ms 650140 KB Output is correct
14 Correct 455 ms 650104 KB Output is correct
15 Correct 480 ms 646320 KB Output is correct
16 Correct 433 ms 648928 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 528 ms 643784 KB Output is correct
2 Correct 516 ms 643808 KB Output is correct
3 Correct 465 ms 644024 KB Output is correct
4 Correct 446 ms 644476 KB Output is correct
5 Correct 462 ms 650080 KB Output is correct
6 Correct 451 ms 650080 KB Output is correct
7 Correct 475 ms 649988 KB Output is correct
8 Correct 467 ms 650080 KB Output is correct
9 Correct 504 ms 650104 KB Output is correct
10 Correct 568 ms 650188 KB Output is correct
11 Correct 458 ms 650208 KB Output is correct
12 Correct 565 ms 650120 KB Output is correct
13 Correct 552 ms 650140 KB Output is correct
14 Correct 455 ms 650104 KB Output is correct
15 Correct 480 ms 646320 KB Output is correct
16 Correct 433 ms 648928 KB Output is correct
17 Correct 478 ms 650076 KB Output is correct
18 Correct 477 ms 650112 KB Output is correct
19 Correct 484 ms 650228 KB Output is correct
20 Correct 497 ms 650208 KB Output is correct
21 Correct 527 ms 650328 KB Output is correct
22 Correct 484 ms 650232 KB Output is correct
23 Correct 516 ms 650204 KB Output is correct
24 Correct 478 ms 650208 KB Output is correct
25 Correct 645 ms 650240 KB Output is correct
26 Correct 475 ms 650208 KB Output is correct
27 Correct 446 ms 646908 KB Output is correct
28 Correct 462 ms 649464 KB Output is correct
29 Correct 486 ms 649460 KB Output is correct

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 528 ms 643784 KB Output is correct
2 Correct 516 ms 643808 KB Output is correct
3 Correct 465 ms 644024 KB Output is correct
4 Correct 446 ms 644476 KB Output is correct
5 Correct 462 ms 650080 KB Output is correct
6 Correct 451 ms 650080 KB Output is correct
7 Correct 475 ms 649988 KB Output is correct
8 Correct 467 ms 650080 KB Output is correct
9 Correct 504 ms 650104 KB Output is correct
10 Correct 568 ms 650188 KB Output is correct
11 Correct 458 ms 650208 KB Output is correct
12 Correct 565 ms 650120 KB Output is correct
13 Correct 552 ms 650140 KB Output is correct
14 Correct 455 ms 650104 KB Output is correct
15 Correct 480 ms 646320 KB Output is correct
16 Correct 433 ms 648928 KB Output is correct
17 Correct 478 ms 650076 KB Output is correct
18 Correct 477 ms 650112 KB Output is correct
19 Correct 484 ms 650228 KB Output is correct
20 Correct 497 ms 650208 KB Output is correct
21 Correct 527 ms 650328 KB Output is correct
22 Correct 484 ms 650232 KB Output is correct
23 Correct 516 ms 650204 KB Output is correct
24 Correct 478 ms 650208 KB Output is correct
25 Correct 645 ms 650240 KB Output is correct
26 Correct 475 ms 650208 KB Output is correct
27 Correct 446 ms 646908 KB Output is correct
28 Correct 462 ms 649464 KB Output is correct
29 Correct 486 ms 649460 KB Output is correct
30 Runtime error 2118 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -