#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;
}
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;
}
}
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){
for(i=1;i<(n+1)*4+4;i+=2){
if(przecina(ij, i) && oYs[i].dist==0){
oYs[i].dist = oXs[ij].dist+1;
kolejka.push(i);
}
}
}
else{
for(i=0;i<(n+1)*4+4;i+=2){
if(przecina(i, ij) && oXs[i].dist==0){
oXs[i].dist = oYs[ij].dist+1;
kolejka.push(i);
}
}
}
}
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:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
29 ms |
600 KB |
Output is correct |
6 |
Correct |
28 ms |
600 KB |
Output is correct |
7 |
Correct |
25 ms |
600 KB |
Output is correct |
8 |
Correct |
27 ms |
604 KB |
Output is correct |
9 |
Correct |
28 ms |
712 KB |
Output is correct |
10 |
Correct |
27 ms |
600 KB |
Output is correct |
11 |
Correct |
28 ms |
600 KB |
Output is correct |
12 |
Correct |
26 ms |
604 KB |
Output is correct |
13 |
Correct |
27 ms |
604 KB |
Output is correct |
14 |
Correct |
28 ms |
776 KB |
Output is correct |
15 |
Correct |
4 ms |
604 KB |
Output is correct |
16 |
Correct |
13 ms |
744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
29 ms |
600 KB |
Output is correct |
6 |
Correct |
28 ms |
600 KB |
Output is correct |
7 |
Correct |
25 ms |
600 KB |
Output is correct |
8 |
Correct |
27 ms |
604 KB |
Output is correct |
9 |
Correct |
28 ms |
712 KB |
Output is correct |
10 |
Correct |
27 ms |
600 KB |
Output is correct |
11 |
Correct |
28 ms |
600 KB |
Output is correct |
12 |
Correct |
26 ms |
604 KB |
Output is correct |
13 |
Correct |
27 ms |
604 KB |
Output is correct |
14 |
Correct |
28 ms |
776 KB |
Output is correct |
15 |
Correct |
4 ms |
604 KB |
Output is correct |
16 |
Correct |
13 ms |
744 KB |
Output is correct |
17 |
Correct |
27 ms |
856 KB |
Output is correct |
18 |
Correct |
26 ms |
856 KB |
Output is correct |
19 |
Correct |
28 ms |
860 KB |
Output is correct |
20 |
Correct |
26 ms |
856 KB |
Output is correct |
21 |
Correct |
29 ms |
860 KB |
Output is correct |
22 |
Correct |
29 ms |
860 KB |
Output is correct |
23 |
Correct |
28 ms |
860 KB |
Output is correct |
24 |
Correct |
30 ms |
860 KB |
Output is correct |
25 |
Correct |
27 ms |
916 KB |
Output is correct |
26 |
Correct |
27 ms |
860 KB |
Output is correct |
27 |
Correct |
6 ms |
604 KB |
Output is correct |
28 |
Correct |
16 ms |
600 KB |
Output is correct |
29 |
Correct |
17 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
29 ms |
600 KB |
Output is correct |
6 |
Correct |
28 ms |
600 KB |
Output is correct |
7 |
Correct |
25 ms |
600 KB |
Output is correct |
8 |
Correct |
27 ms |
604 KB |
Output is correct |
9 |
Correct |
28 ms |
712 KB |
Output is correct |
10 |
Correct |
27 ms |
600 KB |
Output is correct |
11 |
Correct |
28 ms |
600 KB |
Output is correct |
12 |
Correct |
26 ms |
604 KB |
Output is correct |
13 |
Correct |
27 ms |
604 KB |
Output is correct |
14 |
Correct |
28 ms |
776 KB |
Output is correct |
15 |
Correct |
4 ms |
604 KB |
Output is correct |
16 |
Correct |
13 ms |
744 KB |
Output is correct |
17 |
Correct |
27 ms |
856 KB |
Output is correct |
18 |
Correct |
26 ms |
856 KB |
Output is correct |
19 |
Correct |
28 ms |
860 KB |
Output is correct |
20 |
Correct |
26 ms |
856 KB |
Output is correct |
21 |
Correct |
29 ms |
860 KB |
Output is correct |
22 |
Correct |
29 ms |
860 KB |
Output is correct |
23 |
Correct |
28 ms |
860 KB |
Output is correct |
24 |
Correct |
30 ms |
860 KB |
Output is correct |
25 |
Correct |
27 ms |
916 KB |
Output is correct |
26 |
Correct |
27 ms |
860 KB |
Output is correct |
27 |
Correct |
6 ms |
604 KB |
Output is correct |
28 |
Correct |
16 ms |
600 KB |
Output is correct |
29 |
Correct |
17 ms |
604 KB |
Output is correct |
30 |
Execution timed out |
10055 ms |
41460 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |