oj.uz

Submission #45246

# Submission time Handle Problem Language Result Execution time Memory
45246 2018-04-12T05:58:04 Z gs14004 Golf (JOI17_golf) C++17
30 / 100
 2353 ms 992272 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 = 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;
	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;
		update(pos, s, m, tree[prv].l, tree[cur].l, v);
	}
	else{
		tree[cur].l = tree[prv].l;
		tree[cur].r = piv++;
		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, deque<int> &que){
	if(e < ps || pe < s) return;
	if(s <= ps && pe <= e){
		if(dis[p] > dis[v] + 1){
			dis[p] = dis[v] + 1;
			que.push_back(p);
		}
		return;
	}
	int pm = (ps+pe)/2;
	query(s, e, ps, pm, tree[p].l, v, que);
	query(s, e, pm+1, pe, tree[p].r, v, que);
}

int n, sx, sy;
pi s, e;
struct rect{ int sx, ex, sy, ey; }a[100005];
struct seg { int x, s, e, idx; }intv[400500];
vector<seg> segx, segy;

vector<pi> addE[MAXN];

vector<int> solve(vector<seg> &l){
	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);
	vector<int> ans;
	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;
		}
		ans.push_back(crt);
	}
	return ans;
}

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;
}

bool chk[400505];

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;
	});
	auto xpers = solve(segy);
	auto ypers = solve(segx);
	deque<int> que;
	memset(dis, 0x3f, sizeof(dis));
	for(auto &i : segx){
		intv[i.idx] = i;
		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){ // y parallel
		intv[i.idx] = i;
		chk[i.idx] = 1;
		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;
		if(tree[x].l && dis[tree[x].l] > dis[x]){
			dis[tree[x].l] = dis[x];
			que.push_front(tree[x].l);
		}
		if(tree[x].r && dis[tree[x].r] > dis[x]){
			dis[tree[x].r] = dis[x];
			que.push_front(tree[x].r);
		}
		for(auto &i : gph[x]){
			if(dis[i] > dis[x]){
				dis[i] = dis[x];
				que.push_front(i);
			}
		}
		if(x < segx.size() + segy.size()){
			if(chk[x]){
				int nd = ypers[intv[x].x];
				query(intv[x].s, intv[x].e, 0, MAXN-1, nd, x, que);
			}
			else{
				int nd = xpers[intv[x].x];
				query(intv[x].s, intv[x].e, 0, MAXN-1, nd, x, que);
			}
		}
	}
	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 'std::vector<seg> sweep(std::vector<std::pair<int, int> >&)':
golf.cpp:99: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:204:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(x < segx.size() + segy.size()){
      ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:116: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 296 ms 460748 KB Output is correct
2 Correct 344 ms 460780 KB Output is correct
3 Correct 299 ms 460848 KB Output is correct
4 Correct 332 ms 460920 KB Output is correct
5 Correct 319 ms 462444 KB Output is correct
6 Correct 305 ms 462556 KB Output is correct
7 Correct 320 ms 462464 KB Output is correct
8 Correct 355 ms 462596 KB Output is correct
9 Correct 326 ms 462532 KB Output is correct
10 Correct 306 ms 462480 KB Output is correct
11 Correct 307 ms 462556 KB Output is correct
12 Correct 309 ms 462556 KB Output is correct
13 Correct 320 ms 462520 KB Output is correct
14 Correct 291 ms 462620 KB Output is correct
15 Correct 321 ms 461428 KB Output is correct
16 Correct 392 ms 462320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 460748 KB Output is correct
2 Correct 344 ms 460780 KB Output is correct
3 Correct 299 ms 460848 KB Output is correct
4 Correct 332 ms 460920 KB Output is correct
5 Correct 319 ms 462444 KB Output is correct
6 Correct 305 ms 462556 KB Output is correct
7 Correct 320 ms 462464 KB Output is correct
8 Correct 355 ms 462596 KB Output is correct
9 Correct 326 ms 462532 KB Output is correct
10 Correct 306 ms 462480 KB Output is correct
11 Correct 307 ms 462556 KB Output is correct
12 Correct 309 ms 462556 KB Output is correct
13 Correct 320 ms 462520 KB Output is correct
14 Correct 291 ms 462620 KB Output is correct
15 Correct 321 ms 461428 KB Output is correct
16 Correct 392 ms 462320 KB Output is correct
17 Correct 323 ms 462548 KB Output is correct
18 Correct 394 ms 462528 KB Output is correct
19 Correct 393 ms 462636 KB Output is correct
20 Correct 360 ms 462540 KB Output is correct
21 Correct 284 ms 462716 KB Output is correct
22 Correct 287 ms 462592 KB Output is correct
23 Correct 314 ms 462716 KB Output is correct
24 Correct 301 ms 462596 KB Output is correct
25 Correct 335 ms 462588 KB Output is correct
26 Correct 321 ms 462636 KB Output is correct
27 Correct 317 ms 461604 KB Output is correct
28 Correct 299 ms 462492 KB Output is correct
29 Correct 318 ms 462328 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 460748 KB Output is correct
2 Correct 344 ms 460780 KB Output is correct
3 Correct 299 ms 460848 KB Output is correct
4 Correct 332 ms 460920 KB Output is correct
5 Correct 319 ms 462444 KB Output is correct
6 Correct 305 ms 462556 KB Output is correct
7 Correct 320 ms 462464 KB Output is correct
8 Correct 355 ms 462596 KB Output is correct
9 Correct 326 ms 462532 KB Output is correct
10 Correct 306 ms 462480 KB Output is correct
11 Correct 307 ms 462556 KB Output is correct
12 Correct 309 ms 462556 KB Output is correct
13 Correct 320 ms 462520 KB Output is correct
14 Correct 291 ms 462620 KB Output is correct
15 Correct 321 ms 461428 KB Output is correct
16 Correct 392 ms 462320 KB Output is correct
17 Correct 323 ms 462548 KB Output is correct
18 Correct 394 ms 462528 KB Output is correct
19 Correct 393 ms 462636 KB Output is correct
20 Correct 360 ms 462540 KB Output is correct
21 Correct 284 ms 462716 KB Output is correct
22 Correct 287 ms 462592 KB Output is correct
23 Correct 314 ms 462716 KB Output is correct
24 Correct 301 ms 462596 KB Output is correct
25 Correct 335 ms 462588 KB Output is correct
26 Correct 321 ms 462636 KB Output is correct
27 Correct 317 ms 461604 KB Output is correct
28 Correct 299 ms 462492 KB Output is correct
29 Correct 318 ms 462328 KB Output is correct
30 Correct 2160 ms 638720 KB Output is correct
31 Correct 2225 ms 638740 KB Output is correct
32 Correct 2353 ms 640548 KB Output is correct
33 Correct 2335 ms 640540 KB Output is correct
34 Runtime error 1830 ms 992272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -