oj.uz

Submission #45239

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

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 305 ms 362096 KB Output is correct
2 Correct 278 ms 362080 KB Output is correct
3 Correct 291 ms 362036 KB Output is correct
4 Correct 265 ms 362616 KB Output is correct
5 Correct 361 ms 368376 KB Output is correct
6 Correct 266 ms 368376 KB Output is correct
7 Correct 332 ms 368252 KB Output is correct
8 Correct 395 ms 368352 KB Output is correct
9 Correct 410 ms 368532 KB Output is correct
10 Correct 351 ms 368312 KB Output is correct
11 Correct 425 ms 368352 KB Output is correct
12 Correct 301 ms 368380 KB Output is correct
13 Correct 279 ms 368376 KB Output is correct
14 Correct 292 ms 368376 KB Output is correct
15 Correct 277 ms 364536 KB Output is correct
16 Correct 297 ms 367200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 362096 KB Output is correct
2 Correct 278 ms 362080 KB Output is correct
3 Correct 291 ms 362036 KB Output is correct
4 Correct 265 ms 362616 KB Output is correct
5 Correct 361 ms 368376 KB Output is correct
6 Correct 266 ms 368376 KB Output is correct
7 Correct 332 ms 368252 KB Output is correct
8 Correct 395 ms 368352 KB Output is correct
9 Correct 410 ms 368532 KB Output is correct
10 Correct 351 ms 368312 KB Output is correct
11 Correct 425 ms 368352 KB Output is correct
12 Correct 301 ms 368380 KB Output is correct
13 Correct 279 ms 368376 KB Output is correct
14 Correct 292 ms 368376 KB Output is correct
15 Correct 277 ms 364536 KB Output is correct
16 Correct 297 ms 367200 KB Output is correct
17 Correct 317 ms 368356 KB Output is correct
18 Correct 308 ms 368352 KB Output is correct
19 Correct 303 ms 368376 KB Output is correct
20 Correct 305 ms 368376 KB Output is correct
21 Correct 319 ms 368452 KB Output is correct
22 Correct 319 ms 368376 KB Output is correct
23 Correct 311 ms 368480 KB Output is correct
24 Correct 313 ms 368504 KB Output is correct
25 Correct 315 ms 368376 KB Output is correct
26 Correct 333 ms 368620 KB Output is correct
27 Correct 322 ms 365048 KB Output is correct
28 Correct 303 ms 367688 KB Output is correct
29 Correct 330 ms 367712 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 362096 KB Output is correct
2 Correct 278 ms 362080 KB Output is correct
3 Correct 291 ms 362036 KB Output is correct
4 Correct 265 ms 362616 KB Output is correct
5 Correct 361 ms 368376 KB Output is correct
6 Correct 266 ms 368376 KB Output is correct
7 Correct 332 ms 368252 KB Output is correct
8 Correct 395 ms 368352 KB Output is correct
9 Correct 410 ms 368532 KB Output is correct
10 Correct 351 ms 368312 KB Output is correct
11 Correct 425 ms 368352 KB Output is correct
12 Correct 301 ms 368380 KB Output is correct
13 Correct 279 ms 368376 KB Output is correct
14 Correct 292 ms 368376 KB Output is correct
15 Correct 277 ms 364536 KB Output is correct
16 Correct 297 ms 367200 KB Output is correct
17 Correct 317 ms 368356 KB Output is correct
18 Correct 308 ms 368352 KB Output is correct
19 Correct 303 ms 368376 KB Output is correct
20 Correct 305 ms 368376 KB Output is correct
21 Correct 319 ms 368452 KB Output is correct
22 Correct 319 ms 368376 KB Output is correct
23 Correct 311 ms 368480 KB Output is correct
24 Correct 313 ms 368504 KB Output is correct
25 Correct 315 ms 368376 KB Output is correct
26 Correct 333 ms 368620 KB Output is correct
27 Correct 322 ms 365048 KB Output is correct
28 Correct 303 ms 367688 KB Output is correct
29 Correct 330 ms 367712 KB Output is correct
30 Runtime error 2726 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -