| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1114755 |
2024-11-19T14:35:58 Z |
PVSekhar |
Walk (CEOI06_walk) |
C++14 |
|
47 ms |
6136 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e6 + 2;
const int INF = 2e6 + 2;
// from jiangly's template
const double TOL = 1e-9;
template<class T>
struct Point {
T x;
T y;
Point(const T x_ = 0, const T y_ = 0) : x(x_), y(y_) {}
template<class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
Point &operator+=(const Point &p) & {
x += p.x;
y += p.y;
return *this;
}
Point &operator-=(const Point &p) & {
x -= p.x;
y -= p.y;
return *this;
}
Point &operator*=(const T &v) & {
x *= v;
y *= v;
return *this;
}
Point &operator/=(const T &v) & {
x /= v;
y /= v;
return *this;
}
Point operator-() const {
return Point(-x, -y);
}
friend Point operator+(Point a, const Point &b) {
return a += b;
}
friend Point operator-(Point a, const Point &b) {
return a -= b;
}
friend Point operator*(Point a, const T &b) {
return a *= b;
}
friend Point operator/(Point a, const T &b) {
return a /= b;
}
friend Point operator*(const T &a, Point b) {
return b *= a;
}
// w/o tolerance
// friend bool operator<(const Point &a, const Point &b) {
// return a.x < b.x || (a.x == b.x && a.y < b.y);
// }
// w/ tolerance
friend bool operator<(const Point &a, const Point &b) {
return (a.x < b.x || (abs(a.x - b.x) < TOL && a.y < b.y));
}
friend bool operator>(const Point &a, const Point &b) {
return !(a < b);
}
// without tolerance
friend bool operator==(const Point &a, const Point &b) {
return a.x == b.x && a.y == b.y;
}
friend bool operator!=(const Point &a, const Point &b) {
return !(a.x == b.x && a.y == b.y);
}
// with tolerance
// friend bool operator==(const Point &a, const Point &b) {
// Point<T> p = a - b;
// T len = sqrt(p.x * p.x + p.y * p.y);
// return len < TOL;
// }
// friend bool operator!=(const Point &a, const Point &b) {
// Point<T> p = a - b;
// T len = sqrt(p.x * p.x + p.y * p.y);
// return !(len < TOL);
// }
friend std::istream &operator>>(std::istream &is, Point &p) {
return is >> p.x >> p.y;
}
friend std::ostream &operator<<(std::ostream &os, const Point &p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
//For sweep line
// struct Segment{
// ll x1, y1, x2, y2, ind;
// double coordinate() const {
// if (x1 == x2) { return y1; }
// return y1 + 1.0 * (y2 - y1) * (cur_x - x1) / (x2 - x1);
// }
// bool operator<(Segment const& o) const {
// return ind != o.ind && (coordinate() <= o.coordinate());
// }
// bool operator==(const Segment &l) const {
// return ind == l.ind;
// }
// };
using Pt = Point<int>;
int cur_x = 0, x, y, n;
vector<Pt> pts;
map<Pt, Pt> par; // x, y
map<Pt, ll> dis; // x, y
set<pair<int, int>> store; // y, x
void update(Pt &p, pair<int, int> &near) {
if (near.first == p.y) store.erase(near);
if (near.second != p.x) par[p] = Pt(near.second, near.first);
else par[p] = par[Pt(near.second, near.first)];
}
void solve(Pt &p) {
pair<int, int> l = make_pair(-1, -1), r = make_pair(-1, -1);
auto it = store.end();
it = upper_bound(store.begin(), store.end(), make_pair(p.y, INF));
if (it != store.begin()) l = *(--it);
it = upper_bound(store.begin(), store.end(), make_pair(p.y, -1));
if (it != store.end()) r = *it;
if (l.first == -1 && r.first == -1) {
store.insert(make_pair(p.y, p.x));
return;
}
// cout << p.x << " " << p.y << " l: " << l.first << " " << l.second << " r: " << r.first << " " << r.second << "\n";
if (l.first == -1) {
dis[p] = dis[Pt(r.second, r.first)] + abs(p.y - r.first);
update(p, r);
} else if (r.first == -1) {
dis[p] = dis[Pt(l.second, l.first)] + abs(p.y - l.first);
update(p, l);
} else {
ll d1 = dis[Pt(l.second, l.first)] + abs(p.y - l.first), d2 = dis[Pt(r.second, r.first)] + abs(p.y - r.first);
if (d1 <= d2) {
dis[p] = d1;
update(p, l);
} else {
dis[p] = d2;
update(p, r);
}
}
store.insert(make_pair(p.y, p.x));
}
void solve(Pt &p, Pt &q) {
solve(p);
solve(q);
auto it = store.find(make_pair(q.y, q.x));
pair<int, int> pa = make_pair(p.y, p.x);
while (*(--it) != pa) {
store.erase(*it);
}
}
void solve() {
ll x1, y1, x2, y2;
cin >> x >> y >> n;
y += N;
for (int i = 0; i < n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
y1 += N;
y2 += N;
pts.push_back(Pt(x1 - 1, y1 - 1));
pts.push_back(Pt(x1 - 1, y2 + 1));
}
sort(pts.begin(), pts.end());
store.insert(make_pair(N, 0));
dis[Pt(N, 0)] = 0;
for (int i = 0; i < 2 * n; i += 2) {
if (pts[i].x == x) break;
solve(pts[i], pts[i + 1]);
}
Pt dest = Pt(x, y), prev;
solve(dest);
cout << dis[dest] + x << "\n";
stack<Pt> st;
st.push(Pt(dest.x, dest.y - N));
while (dest != Pt(0, N)) {
dest = par[dest];
st.push(Pt(dest.x, dest.y - N));
}
vector<pair<int, int>> ans;
deque<pair<int, int>> dir;
prev = Pt(0, 0);
st.pop();
while (!st.empty()) {
dest = st.top();
// cout << dest.x << " " << dest.y << " " << prev.x << " " << prev.y << "\n";
ans.push_back(make_pair(dest.x - prev.x, 0ll));
ans.push_back(make_pair(0ll, dest.y - prev.y));
st.pop();
prev = dest;
}
dir.push_back(ans[0]);
for (int i = 0; i + 1 < ans.size(); i += 2) {
if (ans[i] != make_pair(0, 0)) {
dir.push_back(ans[i + 1]);
} else {
dir.pop_back();
if (dir.empty()) dir.push_back(ans[i + 1]);
else dir.back().second += ans[i + 1].second;
}
if (i + 2 < ans.size()) dir.push_back(ans[i + 2]);
}
if (dir.back() == make_pair(0, 0)) dir.pop_back();
cout << dir.size() << "\n";
while (!dir.empty()) {
cout << dir.front().first << " " << dir.front().second << "\n";
dir.pop_front();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
Compilation message
walk.cpp: In function 'void solve()':
walk.cpp:212:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
212 | for (int i = 0; i + 1 < ans.size(); i += 2) {
| ~~~~~~^~~~~~~~~~~~
walk.cpp:220:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | if (i + 2 < ans.size()) dir.push_back(ans[i + 2]);
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
35 ms |
4800 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
13 ms |
1756 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
20 ms |
2412 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
47 ms |
5312 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
39 ms |
4800 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
41 ms |
6136 KB |
Execution killed with signal 11 |
