| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1115603 |
2024-11-20T16:51:09 Z |
PVSekhar |
Walk (CEOI06_walk) |
C++17 |
|
1000 ms |
27328 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);
}
friend bool operator<=(const Point &a, const Point &b) {
return a < b || a == b;
}
friend bool operator>=(const Point &a, const Point &b) {
return a > b || a == b;
}
// 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 << ")";
}
};
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 (p == Pt(near.second, near.first)) return;
par[p] = 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) {
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));
if (it == store.end()) {
return;
}
pair<int, int> pa = make_pair(p.y, p.x);
vector<pair<int, int>> temp;
while (*(--it) != pa) {
temp.push_back(*it);
}
for (auto x : temp) store.erase(x);
}
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;
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
y1 += N;
y2 += N;
pts.push_back(Pt(x1 - 1, y1 - 1));
pts.push_back(Pt(x1 - 1, y2 + 1));
}
pts.push_back(Pt(x, y));
sort(pts.begin(), pts.end());
store.insert(make_pair(N, 0));
dis[Pt(0, N)] = 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;
prev = st.top();
st.pop();
while (!st.empty()) {
dest = st.top();
if (dest.x != prev.x) {
if (ans.size() && ans.back().second == 0) ans.back().first += dest.x - prev.x;
else ans.push_back(make_pair(dest.x - prev.x, 0));
}
if (dest.y != prev.y) {
if (ans.size() && ans.back().first == 0) ans.back().second += dest.y - prev.y;
else ans.push_back(make_pair(0, dest.y - prev.y));
}
prev = dest;
st.pop();
}
cout << ans.size() << "\n";
for (auto x : ans) {
cout << x.first << " " << x.second << "\n";
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
4 ms |
592 KB |
Output is correct |
| 5 |
Correct |
233 ms |
25472 KB |
Output is correct |
| 6 |
Correct |
109 ms |
9144 KB |
Output is correct |
| 7 |
Correct |
465 ms |
14404 KB |
Output is correct |
| 8 |
Execution timed out |
1064 ms |
8124 KB |
Time limit exceeded |
| 9 |
Correct |
285 ms |
27072 KB |
Output is correct |
| 10 |
Correct |
316 ms |
27328 KB |
Output is correct |
