oj.uz

Submission #45238

# Submission time Handle Problem Language Result Execution time Memory
45238 2018-04-12T05:25:57 Z gs14004 Golf (JOI17_golf) C++17
30 / 100
 2534 ms 1048576 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 = 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

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

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

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