oj.uz

Submission #1003546

# Submission time Handle Problem Language Result Execution time Memory
1003546 2024-06-20T12:45:35 Z jamjanek Golf (JOI17_golf) C++14
100 / 100
 2608 ms 313008 KB 
#include<bits/stdc++.h>
using namespace std;
map<int,int>mapx, mapy;
struct rect{int a, b, c, d; int id;};
vector<rect>pros;
bool cmp1(rect a, rect b){
	return a.a < b.a;
}

bool cmp2(rect a, rect b){
	return a.c < b.c;
}
bool cmp3(rect a, rect b){
	return a.b > b.b;
}
bool cmp4(rect a, rect b){
	return a.d > b.d;
}
struct oX{int x, p, k, id, dist;};
struct oY{int y, p, k, id, dist;};
oX oXs[400010];
oY oYs[400010];
bool przecina(int x, int y){
	if(oXs[x].p<=oYs[y].y && oXs[x].k>=oYs[y].y && oYs[y].p<=oXs[x].x && oYs[y].k>=oXs[x].x)
		return 1;
	return 0;
}
const int base = 1<<18;
int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int val){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w] = val;
		return;
	}
	if(tree[w]!=-1)
		tree[w*2] = tree[w*2+1] = tree[w];
	tree[w] = -1;
	ustaw(w*2, l, (l+p)/2, a, b, val);
	ustaw(w*2+1, (l+p)/2+1, p, a, b, val);
}
int value(int w){
	int ans = -1;
	w+=base;
	while(w>0){
		if(tree[w]!=-1)
			ans = tree[w];
		w/=2;
	}
	return ans;
}

set<pair<int,int>>treex[2*base], treey[2*base];
void dodajx(int w, int l, int p, int a, int b, int val1, int val2){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		treex[w].insert({val1, val2});
		return;
	}
	dodajx(w*2, l, (l+p)/2, a, b, val1, val2);
	dodajx(w*2+1, (l+p)/2+1, p, a, b, val1, val2);
}
void dodajy(int w, int l, int p, int a, int b, int val1, int val2){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		treey[w].insert({val1, val2});
		return;
	}
	dodajy(w*2, l, (l+p)/2, a, b, val1, val2);
	dodajy(w*2+1, (l+p)/2+1, p, a, b, val1, val2);
}
int main()
{
	int sx, sy, tx, ty, n, i;
	scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
	mapx[sx]=0;
	mapx[tx]=0;
	mapy[sy]=0;
	mapy[ty]=0;
	for(i=0;i<n;i++){
		pros.push_back({});
		scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
		mapx[pros.back().a] = mapx[pros.back().b] = 0;
		mapy[pros.back().c] = mapy[pros.back().d] = 0;
	}
	i = 0;
	for(auto &ij: mapx)
		ij.second = i++;
	i = 0;
	for(auto &ij: mapy)
		ij.second = i++;
	sx = mapx[sx];
	tx = mapx[tx];
	sy = mapy[sy];
	ty = mapy[ty];
	for(auto &ij: pros){
		ij.a = mapx[ij.a];
		ij.b = mapx[ij.b];
		ij.c = mapy[ij.c];
		ij.d = mapy[ij.d];
	}
	pros.push_back({sx, sx, sy, sy});//start ma id n
	pros.push_back({tx, tx, ty, ty});//koniec ma id n+1
	for(i=0;i<n+2;i++){
		pros[i].id = i;
		oXs[i*4+0].x = pros[i].a;
		oYs[i*4+1].y = pros[i].c;
		oXs[i*4+2].x = pros[i].b;
		oYs[i*4+3].y = pros[i].d;
	}
	sort(pros.begin(), pros.end(), cmp1);
	ustaw(1, 0, base-1, 0, 2*(n+1), 0);
	for(auto &ij: pros){
		oYs[ij.id*4+1].p = value(ij.c);
		oYs[ij.id*4+3].p = value(ij.d);
		ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.b);
	}
	sort(pros.begin(), pros.end(), cmp2);
	ustaw(1, 0, base-1, 0, 2*(n+1), 0);
	for(auto &ij: pros){
		oXs[ij.id*4+0].p = value(ij.a);
		oXs[ij.id*4+2].p = value(ij.b);
		ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.d);
	}
	sort(pros.begin(), pros.end(), cmp3);
	ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
	for(auto &ij: pros){
		oYs[ij.id*4+1].k = value(ij.c);
		oYs[ij.id*4+3].k = value(ij.d);
		ustaw(1, 0, base-1, ij.c+1, ij.d-1, ij.a);
	}
	sort(pros.begin(), pros.end(), cmp4);
	ustaw(1, 0, base-1, 0, 2*(n+1), 2*(n+1));
	for(auto &ij: pros){
		oXs[ij.id*4+0].k = value(ij.a);
		oXs[ij.id*4+2].k = value(ij.b);
		ustaw(1, 0, base-1, ij.a+1, ij.b-1, ij.c);
	}
	
	if(sx==tx){
		if(oXs[n*4+0].p<=ty && oXs[n*4+0].k>=ty){
			printf("1\n");return 0;
		}
	}
	
	if(sy==ty){
		if(oYs[n*4+1].p<=tx && oYs[n*4+1].k>=tx){
			printf("1\n");return 0;
		}
	}
	for(i=0;i<(n+2)*4;i+=2){
		if(i!= n*4+0 && i!=n*4+2){
			dodajx(1, 0, base-1, oXs[i].p, oXs[i].k, oXs[i].x, i);
		}
	}
	for(i=1;i<(n+2)*4;i+=2){
		if(i!= n*4+1 && i!=n*4+3){
			dodajy(1, 0, base-1, oYs[i].p, oYs[i].k, oYs[i].y, i);
		}
	}
	queue<int>kolejka;
	oXs[n*4+0].dist = 1;
	oXs[n*4+2].dist = 1;
	oYs[n*4+1].dist = 1;
	oYs[n*4+3].dist = 1;
	kolejka.push(n*4+0);
	kolejka.push(n*4+1);
	kolejka.push(n*4+2);
	kolejka.push(n*4+3);
	while(kolejka.size()){
		auto ij = kolejka.front();
		kolejka.pop();
		if(ij%2==0){
			auto A = oXs[ij];
			int pom = A.x+base;
			while(pom>0){
				while(treey[pom].lower_bound({A.p, 0})!=treey[pom].end() && (*treey[pom].lower_bound({A.p, 0})).first<=A.k){
					auto pom2 = *treey[pom].lower_bound({A.p, 0});
					treey[pom].erase(pom2);
					if(oYs[pom2.second].dist==0){
						oYs[pom2.second].dist = A.dist+1;
						kolejka.push(pom2.second);
					}
				}
				pom/=2;
			}
		}
		else{
			auto A = oYs[ij];
			int pom = A.y+base;
			while(pom>0){
				while(treex[pom].lower_bound({A.p, 0})!=treex[pom].end() && (*treex[pom].lower_bound({A.p, 0})).first<=A.k){
					auto pom2 = *treex[pom].lower_bound({A.p, 0});
					treex[pom].erase(pom2);
					if(oXs[pom2.second].dist==0){
						oXs[pom2.second].dist = A.dist+1;
						kolejka.push(pom2.second);
					}
				}
				pom/=2;
			}
		}
	}
	printf("%d\n", min({oXs[(n+1)*4+0].dist, oXs[(n+1)*4+2].dist, oYs[(n+1)*4+1].dist, oYs[(n+1)*4+3].dist}));
	/*
	printf("X:\n");
	for(i=0;i<=(n+1);i++){
		printf("%d %d %d %d %d\n", oXs[i*4+0].x, oXs[i*4+0].p, oXs[i*4+0].k, oXs[i*4+0].id, oXs[i*4+0].dist);
		printf("%d %d %d %d %d\n", oXs[i*4+2].x, oXs[i*4+2].p, oXs[i*4+2].k, oXs[i*4+2].id, oXs[i*4+2].dist);
	}
	printf("Y:\n");
	for(i=0;i<=(n+1);i++){
		printf("%d %d %d %d %d\n", oYs[i*4+1].y, oYs[i*4+1].p, oYs[i*4+1].k, oYs[i*4+1].id, oYs[i*4+1].dist);
		printf("%d %d %d %d %d\n", oYs[i*4+3].y, oYs[i*4+3].p, oYs[i*4+3].k, oYs[i*4+3].id, oYs[i*4+3].dist);
	}*/
}

Compilation message

golf.cpp: In function 'int main()':
golf.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49496 KB Output is correct
2 Correct 21 ms 49488 KB Output is correct
3 Correct 20 ms 49756 KB Output is correct
4 Correct 20 ms 49756 KB Output is correct
5 Correct 25 ms 50972 KB Output is correct
6 Correct 25 ms 51036 KB Output is correct
7 Correct 25 ms 51036 KB Output is correct
8 Correct 25 ms 51036 KB Output is correct
9 Correct 25 ms 51036 KB Output is correct
10 Correct 26 ms 51288 KB Output is correct
11 Correct 25 ms 51036 KB Output is correct
12 Correct 25 ms 51288 KB Output is correct
13 Correct 24 ms 51036 KB Output is correct
14 Correct 30 ms 51036 KB Output is correct
15 Correct 21 ms 50268 KB Output is correct
16 Correct 25 ms 51288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49496 KB Output is correct
2 Correct 21 ms 49488 KB Output is correct
3 Correct 20 ms 49756 KB Output is correct
4 Correct 20 ms 49756 KB Output is correct
5 Correct 25 ms 50972 KB Output is correct
6 Correct 25 ms 51036 KB Output is correct
7 Correct 25 ms 51036 KB Output is correct
8 Correct 25 ms 51036 KB Output is correct
9 Correct 25 ms 51036 KB Output is correct
10 Correct 26 ms 51288 KB Output is correct
11 Correct 25 ms 51036 KB Output is correct
12 Correct 25 ms 51288 KB Output is correct
13 Correct 24 ms 51036 KB Output is correct
14 Correct 30 ms 51036 KB Output is correct
15 Correct 21 ms 50268 KB Output is correct
16 Correct 25 ms 51288 KB Output is correct
17 Correct 30 ms 51280 KB Output is correct
18 Correct 29 ms 51288 KB Output is correct
19 Correct 28 ms 51292 KB Output is correct
20 Correct 26 ms 51264 KB Output is correct
21 Correct 27 ms 51288 KB Output is correct
22 Correct 27 ms 51284 KB Output is correct
23 Correct 37 ms 51284 KB Output is correct
24 Correct 26 ms 51292 KB Output is correct
25 Correct 26 ms 51276 KB Output is correct
26 Correct 27 ms 51368 KB Output is correct
27 Correct 21 ms 50520 KB Output is correct
28 Correct 25 ms 51288 KB Output is correct
29 Correct 24 ms 51284 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49496 KB Output is correct
2 Correct 21 ms 49488 KB Output is correct
3 Correct 20 ms 49756 KB Output is correct
4 Correct 20 ms 49756 KB Output is correct
5 Correct 25 ms 50972 KB Output is correct
6 Correct 25 ms 51036 KB Output is correct
7 Correct 25 ms 51036 KB Output is correct
8 Correct 25 ms 51036 KB Output is correct
9 Correct 25 ms 51036 KB Output is correct
10 Correct 26 ms 51288 KB Output is correct
11 Correct 25 ms 51036 KB Output is correct
12 Correct 25 ms 51288 KB Output is correct
13 Correct 24 ms 51036 KB Output is correct
14 Correct 30 ms 51036 KB Output is correct
15 Correct 21 ms 50268 KB Output is correct
16 Correct 25 ms 51288 KB Output is correct
17 Correct 30 ms 51280 KB Output is correct
18 Correct 29 ms 51288 KB Output is correct
19 Correct 28 ms 51292 KB Output is correct
20 Correct 26 ms 51264 KB Output is correct
21 Correct 27 ms 51288 KB Output is correct
22 Correct 27 ms 51284 KB Output is correct
23 Correct 37 ms 51284 KB Output is correct
24 Correct 26 ms 51292 KB Output is correct
25 Correct 26 ms 51276 KB Output is correct
26 Correct 27 ms 51368 KB Output is correct
27 Correct 21 ms 50520 KB Output is correct
28 Correct 25 ms 51288 KB Output is correct
29 Correct 24 ms 51284 KB Output is correct
30 Correct 2400 ms 276056 KB Output is correct
31 Correct 2301 ms 276104 KB Output is correct
32 Correct 2509 ms 278016 KB Output is correct
33 Correct 2457 ms 278300 KB Output is correct
34 Correct 2354 ms 280536 KB Output is correct
35 Correct 2319 ms 280268 KB Output is correct
36 Correct 2334 ms 280284 KB Output is correct
37 Correct 2291 ms 279608 KB Output is correct
38 Correct 2344 ms 280620 KB Output is correct
39 Correct 2332 ms 279516 KB Output is correct
40 Correct 2356 ms 312936 KB Output is correct
41 Correct 2608 ms 313008 KB Output is correct
42 Correct 1998 ms 259760 KB Output is correct
43 Correct 2041 ms 259844 KB Output is correct
44 Correct 1903 ms 242968 KB Output is correct
45 Correct 1892 ms 243268 KB Output is correct
46 Correct 1877 ms 243232 KB Output is correct
47 Correct 1712 ms 243036 KB Output is correct
48 Correct 1738 ms 243168 KB Output is correct
49 Correct 1763 ms 243260 KB Output is correct
50 Correct 39 ms 51284 KB Output is correct
51 Correct 28 ms 51292 KB Output is correct
52 Correct 24 ms 51284 KB Output is correct