| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 253288 |
2020-07-27T15:49:19 Z |
kostia244 |
Golf (JOI17_golf) |
C++17 |
|
396 ms |
160464 KB |
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
const int maxn = 4040;
using pt = array<int, 2>;
vector<int> x, y;
int n, dist[maxn][maxn][2], bad[maxn][maxn], a[maxn], b[maxn], c[maxn], d[maxn];
pt st, en;
void inc(int xl, int xr, int yl, int yr) {
if(xl >= xr || yl >= yr) return;
bad[xl][yl]++;
bad[xl][yr]--;
bad[xr][yl]--;
bad[xr][yr]++;
}
void dbl(vector<int> &f) {
vector<int> x;
for(auto i : f)
for(int j = 0 ;j < 2; j++)
x.push_back(i);
f = x;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> st[0] >> st[1] >> en[0] >> en[1] >> n;
x.push_back(st[0]);
x.push_back(en[0]);
y.push_back(st[1]);
y.push_back(en[1]);
for(int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
x.push_back(a[i]);
x.push_back(b[i]);
y.push_back(c[i]);
y.push_back(d[i]);
}
sort(all(x)), sort(all(y));
x.erase(unique(all(x)), x.end());
y.erase(unique(all(y)), y.end());
dbl(x), dbl(y);
st[0] = lower_bound(all(x), st[0]) - x.begin();
st[1] = lower_bound(all(y), st[1]) - y.begin();
en[0] = lower_bound(all(x), en[0]) - x.begin();
en[1] = lower_bound(all(y), en[1]) - y.begin();
for(int i = 0; i < n; i++) {
a[i] = lower_bound(all(x), a[i]) - x.begin();
b[i] = upper_bound(all(x), b[i]) - x.begin() - 1;
c[i] = lower_bound(all(y), c[i]) - y.begin();
d[i] = upper_bound(all(y), d[i]) - y.begin() - 1;
inc(a[i]+1, b[i], c[i]+1, d[i]);
}
for(int i = 0; i < x.size(); i++) {
for(int j = 0; j < y.size(); j++) {
if(i) bad[i][j] += bad[i-1][j];
if(j) bad[i][j] += bad[i][j-1];
if(i&&j) bad[i][j] -= bad[i-1][j-1];
}
}
vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
priority_queue<array<ll, 4>> pq;
memset(dist, 0x3f, sizeof dist);
dist[st[0]][st[1]][0] = 1;
dist[st[0]][st[1]][1] = 1;
pq.push({-1, 0, st[0], st[1]});
pq.push({-1, 1, st[0], st[1]});
while(!pq.empty()) {
auto [d, dir, X, Y] = pq.top();
pq.pop();
d *= -1;
if(d > dist[X][Y][dir]) continue;
if(X-(X&1) == en[0] && Y-(Y&1) == en[1]) return cout << d << '\n', 0;
for(int i = 0; i < 4; i++) {
int tx = X + dx[i], ty = Y + dy[i], tdir = i/2;
if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
ll c = d + (dir != tdir);
if(c < dist[tx][ty][tdir]) {
dist[tx][ty][tdir] = c;
pq.push({-c, tdir, tx, ty});
}
}
}
}
Compilation message
golf.cpp: In function 'int main()':
golf.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < x.size(); i++) {
~~^~~~~~~~~~
golf.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < y.size(); j++) {
~~^~~~~~~~~~
golf.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
~~~^~~~~~~~~~~
golf.cpp:76:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tx < 0 || tx >= x.size() || ty < 0 || ty >= y.size() || bad[tx][ty]) continue;
~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
128120 KB |
Output is correct |
| 2 |
Correct |
62 ms |
128248 KB |
Output is correct |
| 3 |
Correct |
72 ms |
128376 KB |
Output is correct |
| 4 |
Correct |
70 ms |
130688 KB |
Output is correct |
| 5 |
Correct |
396 ms |
160464 KB |
Output is correct |
| 6 |
Incorrect |
236 ms |
149220 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
128120 KB |
Output is correct |
| 2 |
Correct |
62 ms |
128248 KB |
Output is correct |
| 3 |
Correct |
72 ms |
128376 KB |
Output is correct |
| 4 |
Correct |
70 ms |
130688 KB |
Output is correct |
| 5 |
Correct |
396 ms |
160464 KB |
Output is correct |
| 6 |
Incorrect |
236 ms |
149220 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
128120 KB |
Output is correct |
| 2 |
Correct |
62 ms |
128248 KB |
Output is correct |
| 3 |
Correct |
72 ms |
128376 KB |
Output is correct |
| 4 |
Correct |
70 ms |
130688 KB |
Output is correct |
| 5 |
Correct |
396 ms |
160464 KB |
Output is correct |
| 6 |
Incorrect |
236 ms |
149220 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
