#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<int> store; // y, x
vector<int> x_val(2 * N + 2);
void update(Pt &p, int &near) {
if (near == p.y) store.erase(near);
if (p != Pt(x_val[near], near)) par[p] = Pt(x_val[near], near);
}
void solve(Pt &p) {
int l = -1, r = -1;
auto it = store.end();
it = upper_bound(store.begin(), store.end(), p.y);
if (it != store.begin()) l = *(--it);
if (it != store.end() && (*it) >= p.y) r = *it;
else if ((++it) != store.end()) r = *it;
if (l == -1) {
dis[p] = dis[Pt(x_val[r], r)] + abs(p.y - r);
update(p, r);
} else if (r == -1) {
dis[p] = dis[Pt(x_val[l], l)] + abs(p.y - l);
update(p, l);
} else {
ll d1 = dis[Pt(x_val[l], l)] + abs(p.y - l), d2 = dis[Pt(x_val[r], r)] + abs(p.y - r);
if (d1 <= d2) {
dis[p] = d1;
update(p, l);
} else {
dis[p] = d2;
update(p, r);
}
}
store.insert(p.y);
x_val[p.y] = p.x;
}
void solve(Pt &p, Pt &q) {
solve(p);
solve(q);
auto en = store.find(q.y);
auto st = store.find(p.y);
st++;
if (st != en) store.erase(st, en);
}
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(N);
x_val[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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8272 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8300 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8272 KB |
Output is correct |
| 4 |
Correct |
5 ms |
8696 KB |
Output is correct |
| 5 |
Correct |
206 ms |
33216 KB |
Output is correct |
| 6 |
Correct |
89 ms |
16828 KB |
Output is correct |
| 7 |
Correct |
309 ms |
22292 KB |
Output is correct |
| 8 |
Execution timed out |
1051 ms |
18888 KB |
Time limit exceeded |
| 9 |
Correct |
246 ms |
34492 KB |
Output is correct |
| 10 |
Correct |
251 ms |
35248 KB |
Output is correct |
