| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 823847 |
2023-08-13T08:41:38 Z |
vjudge1 |
Sky Walking (IOI19_walk) |
C++17 |
|
4000 ms |
168712 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
vector<int> A = h, B = h;
for (int i = s + 1; i < A.size(); i++) {
A[i] = max(A[i - 1], A[i]);
}
for (int i = s - 1; i >= 0; i--) {
A[i] = max(A[i + 1], A[i]);
}
for (int i = g + 1; i < B.size(); i++) {
B[i] = max(B[i - 1], B[i]);
}
for (int i = g - 1; i >= 0; i--) {
B[i] = max(B[i + 1], B[i]);
}
int m = l.size();
for (int i = 0; i < m; i++) {
auto get = [&](int x, vector<int> &v, int h) -> tuple<int, int> {
int l = x, r = v.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (v[m] >= h) {
r = m;
} else {
l = m + 1;
}
}
int B = l;
l = 0, r = x;
while (l < r){
int m = (l + r) / 2;
if (v[m + 1] >= h) {
l = m + 1;
} else {
r = m;
}
}
return {l, B};
};
vector<int> v = {l[i], r[i]};
if (l[i] < s && s < r[i]) {
auto [x, y2] = get(s, A, y[i]);
v.push_back(x);
v.push_back(y2);
}
if (l[i] < g && g < r[i]) {
auto [x, y2] = get(g, B, y[i]);
v.push_back(x);
v.push_back(y2);
}
sort(v.begin(), v.end());
for (int j = 1; j < v.size(); j++) {
if (v[j] != v[j - 1]) {
l.push_back(v[j - 1]);
r.push_back(v[j]);
y.push_back(y[i]);
}
}
}
long long inf = 1e18;
vector<map<int, long long>> d(x.size());
vector<map<int, vector<pair<int, int>>>> V(x.size());
unordered_map<int, vector<int>> id;
for (int i = 0; i < x.size(); i++) {
d[i][0] = inf;
}
vector<vector<int>> gg;
for (int i = m; i < l.size(); i++) {
gg.push_back({l[i], y[i]});
gg.push_back({r[i], y[i]});
gg.push_back({l[i], -1, y[i]});
gg.push_back({r[i] + 1, -2, y[i]});
}
sort(gg.begin(), gg.end());
multiset<int> S;
for (auto& shit: gg) {
if (shit[1] == -1) {
S.insert(shit[2]);
} else if (shit[1] == -2) {
S.erase(S.find(shit[2]));
} else {
d[shit[0]][shit[1]] = inf;
auto p = S.lower_bound(shit[1]);
if (p != S.begin()) {
p--;
d[shit[0]][*p] = inf;
}
}
}
d[s][0] = 0;
for (int i = 0; i < x.size(); i++) {
int last = 0;
for (auto p: d[i]) {
id[p.first].push_back(i);
if (p.first == last) {
continue;
}
//cout << i << " " << p.first << " " << i << " " << last << "\n";
V[i][p.first].push_back({i, last});
V[i][last].push_back({i, p.first});
last = p.first;
}
}
unordered_map<int, vector<int>> sid = id;
for (auto&p : sid) {
for (int j = 0; j < p.second.size(); j++) {
p.second[j] = 0;
}
p.second.push_back(0);
}
for (int i = m; i < l.size(); i++) {
// l[i], r[i]
sid[y[i]][lower_bound(id[y[i]].begin(), id[y[i]].end(), l[i]) - id[y[i]].begin()]++;
sid[y[i]][lower_bound(id[y[i]].begin(), id[y[i]].end(), r[i]) - id[y[i]].begin()]--;
}
//cout << "L ";
//for (int i: id[5]) {
// cout << i << " ";
//}
//cout << "\n";
for (auto&p : id) {
auto shit = sid[p.first];
for (int j = 0; j + 1 < shit.size(); j++) {
shit[j + 1] += shit[j];
if (shit[j]) {
//cout << p.second[j] << " " << p.first << " " << p.second[j + 1] << " " << p.first << "\n";
V[p.second[j]][p.first].push_back({p.second[j + 1], p.first});
V[p.second[j + 1]][p.first].push_back({p.second[j], p.first});
}
}
}
auto dist = [&](int x1, int y1, int x2, int y2) -> long long {
return (long long)abs(x[x1] - x[x2]) + abs(y1 - y2);
};
set<pair<int, pair<int, int>>> f;
f.insert({0, {s, 0}});
while (!f.empty()) {
int a = f.begin()->second.first;
int b = f.begin()->second.second;
f.erase(f.begin());
for (auto to: V[a][b]) {
int na = to.first, nb = to.second;
if (d[a][b] + dist(a, b, na ,nb) < d[na][nb]) {
f.erase({d[na][nb], {na, nb}});
d[na][nb] = d[a][b] + dist(a, b, na ,nb);
f.insert({d[na][nb], {na, nb}});
}
}
}
return d[g][0];
}
Compilation message
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:9:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = s + 1; i < A.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i = g + 1; i < B.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = 1; j < v.size(); j++) {
| ~~^~~~~~~~~~
walk.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = m; i < l.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int j = 0; j < p.second.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
walk.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = m; i < l.size(); i++) {
| ~~^~~~~~~~~~
walk.cpp:136:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int j = 0; j + 1 < shit.size(); j++) {
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
904 ms |
120604 KB |
Output is correct |
| 4 |
Execution timed out |
4078 ms |
144504 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
28208 KB |
Output is correct |
| 2 |
Correct |
1291 ms |
131908 KB |
Output is correct |
| 3 |
Correct |
1111 ms |
138032 KB |
Output is correct |
| 4 |
Correct |
1258 ms |
163996 KB |
Output is correct |
| 5 |
Correct |
3084 ms |
168712 KB |
Output is correct |
| 6 |
Correct |
1476 ms |
160776 KB |
Output is correct |
| 7 |
Correct |
554 ms |
95708 KB |
Output is correct |
| 8 |
Correct |
516 ms |
117000 KB |
Output is correct |
| 9 |
Correct |
1811 ms |
157204 KB |
Output is correct |
| 10 |
Correct |
541 ms |
106376 KB |
Output is correct |
| 11 |
Incorrect |
15 ms |
10772 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
28208 KB |
Output is correct |
| 2 |
Correct |
1291 ms |
131908 KB |
Output is correct |
| 3 |
Correct |
1111 ms |
138032 KB |
Output is correct |
| 4 |
Correct |
1258 ms |
163996 KB |
Output is correct |
| 5 |
Correct |
3084 ms |
168712 KB |
Output is correct |
| 6 |
Correct |
1476 ms |
160776 KB |
Output is correct |
| 7 |
Correct |
554 ms |
95708 KB |
Output is correct |
| 8 |
Correct |
516 ms |
117000 KB |
Output is correct |
| 9 |
Correct |
1811 ms |
157204 KB |
Output is correct |
| 10 |
Correct |
541 ms |
106376 KB |
Output is correct |
| 11 |
Incorrect |
15 ms |
10772 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
