oj.uz

Submission #45240

# Submission time Handle Problem Language Result Execution time Memory
45240 2018-04-12T05:32:04 Z gs14004 Golf (JOI17_golf) C++17
30 / 100
 2516 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> 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -