oj.uz

Submission #45236

# Submission time Handle Problem Language Result Execution time Memory
45236 2018-04-12T05:24:35 Z gs14004 Golf (JOI17_golf) C++17
30 / 100
 1888 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 = 15000000;

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 555 ms 796452 KB Output is correct
2 Correct 556 ms 796536 KB Output is correct
3 Correct 540 ms 796588 KB Output is correct
4 Correct 629 ms 797024 KB Output is correct
5 Correct 685 ms 802716 KB Output is correct
6 Correct 677 ms 802680 KB Output is correct
7 Correct 624 ms 802680 KB Output is correct
8 Correct 555 ms 802680 KB Output is correct
9 Correct 529 ms 802808 KB Output is correct
10 Correct 569 ms 802808 KB Output is correct
11 Correct 623 ms 802836 KB Output is correct
12 Correct 565 ms 802912 KB Output is correct
13 Correct 596 ms 802936 KB Output is correct
14 Correct 615 ms 802844 KB Output is correct
15 Correct 524 ms 798936 KB Output is correct
16 Correct 549 ms 801656 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 796452 KB Output is correct
2 Correct 556 ms 796536 KB Output is correct
3 Correct 540 ms 796588 KB Output is correct
4 Correct 629 ms 797024 KB Output is correct
5 Correct 685 ms 802716 KB Output is correct
6 Correct 677 ms 802680 KB Output is correct
7 Correct 624 ms 802680 KB Output is correct
8 Correct 555 ms 802680 KB Output is correct
9 Correct 529 ms 802808 KB Output is correct
10 Correct 569 ms 802808 KB Output is correct
11 Correct 623 ms 802836 KB Output is correct
12 Correct 565 ms 802912 KB Output is correct
13 Correct 596 ms 802936 KB Output is correct
14 Correct 615 ms 802844 KB Output is correct
15 Correct 524 ms 798936 KB Output is correct
16 Correct 549 ms 801656 KB Output is correct
17 Correct 550 ms 802728 KB Output is correct
18 Correct 546 ms 802936 KB Output is correct
19 Correct 595 ms 802808 KB Output is correct
20 Correct 547 ms 802844 KB Output is correct
21 Correct 527 ms 802876 KB Output is correct
22 Correct 544 ms 802936 KB Output is correct
23 Correct 532 ms 802932 KB Output is correct
24 Correct 598 ms 802924 KB Output is correct
25 Correct 568 ms 802856 KB Output is correct
26 Correct 540 ms 802936 KB Output is correct
27 Correct 546 ms 799736 KB Output is correct
28 Correct 583 ms 802076 KB Output is correct
29 Correct 562 ms 802176 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 796452 KB Output is correct
2 Correct 556 ms 796536 KB Output is correct
3 Correct 540 ms 796588 KB Output is correct
4 Correct 629 ms 797024 KB Output is correct
5 Correct 685 ms 802716 KB Output is correct
6 Correct 677 ms 802680 KB Output is correct
7 Correct 624 ms 802680 KB Output is correct
8 Correct 555 ms 802680 KB Output is correct
9 Correct 529 ms 802808 KB Output is correct
10 Correct 569 ms 802808 KB Output is correct
11 Correct 623 ms 802836 KB Output is correct
12 Correct 565 ms 802912 KB Output is correct
13 Correct 596 ms 802936 KB Output is correct
14 Correct 615 ms 802844 KB Output is correct
15 Correct 524 ms 798936 KB Output is correct
16 Correct 549 ms 801656 KB Output is correct
17 Correct 550 ms 802728 KB Output is correct
18 Correct 546 ms 802936 KB Output is correct
19 Correct 595 ms 802808 KB Output is correct
20 Correct 547 ms 802844 KB Output is correct
21 Correct 527 ms 802876 KB Output is correct
22 Correct 544 ms 802936 KB Output is correct
23 Correct 532 ms 802932 KB Output is correct
24 Correct 598 ms 802924 KB Output is correct
25 Correct 568 ms 802856 KB Output is correct
26 Correct 540 ms 802936 KB Output is correct
27 Correct 546 ms 799736 KB Output is correct
28 Correct 583 ms 802076 KB Output is correct
29 Correct 562 ms 802176 KB Output is correct
30 Runtime error 1888 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -