| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1014998 |
2024-07-05T22:40:38 Z |
jamjanek |
Golf (JOI17_golf) |
C++14 |
|
0 ms |
348 KB |
#include<bits/stdc++.h>
using namespace std;
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<<10;
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);
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);
}
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:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d%d%d", &pros.back().a, &pros.back().b, &pros.back().c, &pros.back().d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
