#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, int> pll;
typedef long long ll;
const int N = 1e5+1;
const int S = 1e6+10;
const int K = 4e5+1;
const ll INF = 1e17+1;
int x, y, n;
vector<pii> p, bg[S];
set<int> s;
map<int, int> sc;
ll ans[4*K], par[4*K];
pll T[4*K][2];
bool L[4*K];
void push(int v) {
for (int t=0; t<2; ++t) {
T[2*v][t]=T[2*v+1][t]={INF, INF};
L[2*v]=L[2*v+1]=true;
}
L[v]=false;
}
pll que(int v, int l, int r, int ql, int qr, int t) {
if (l > qr || r < ql) return {INF, INF};
if (L[v]) push(v);
if (l >= ql && r <= qr) return T[v][t];
int m=(l+r)/2;
return min(
que(2*v, l, m, ql, qr, t),
que(2*v+1, m+1, r, ql, qr, t)
);
}
void clear(int v, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return;
if (L[v]) push(v);
if (l >= ql && r <= qr) {
T[v][0]=T[v][1]={INF, INF};
L[v]=true, push(v);
return;
}
int m=(l+r)/2;
clear(2*v, l, m, ql, qr), clear(2*v+1, m+1, r, ql, qr);
T[v][0]=min(T[2*v][0], T[2*v+1][0]);
T[v][1]=min(T[2*v][1], T[2*v+1][1]);
}
void upd(int v, int l, int r, int p, int t, pll x) {
if (l == r) {
T[v][t]=min(T[v][t], x);
return;
}
if (L[v]) push(v);
int m=(l+r)/2;
if (p <= m) upd(2*v, l, m, p, t, x);
else upd(2*v+1, m+1, r, p, t, x);
T[v][t]=min(T[2*v][t], T[2*v+1][t]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>x>>y>>n;
p.push_back({0, 0}), p.push_back({x, y});
memset(par, -1, sizeof(par));
for (int i=1; i<=n; ++i) {
int x1, y1, x2, y2;
cin>>x1>>y1>>x2>>y2;
s.insert(y1), s.insert(y2);
bg[min(x1, x2)].push_back({min(y1, y2), max(y1, y2)});
p.push_back({min(x1, x2)-1, max(y1, y2)+1});
p.push_back({max(x1, x2)+1, max(y1, y2)+1});
p.push_back({max(x1, x2)+1, min(y1, y2)-1});
p.push_back({min(x1, x2)-1, min(y1, y2)-1});
}
for (auto u : p) s.insert(u.second);
int i=1;
for (auto u : s) sc[u]=i++;
sort(p.begin(), p.end());
int sz=p.size();
clear(1, 1, sz, 1, sz);
upd(1, 1, sz, sc[0], 0, {0, 0});
upd(1, 1, sz, sc[0], 1, {0, 0});
ans[0]=0;
int ptr=1, h=1e6;
for (int x=1; x<=h; ++x) {
while (ptr < sz) {
if (p[ptr].first > x) break;
int y=p[ptr].second;
pll low=que(1, 1, sz, 1, sc[y], 0);
pll up=que(1, 1, sz, sc[y], sz, 1);
if (low.first+y <= up.first-y) {
ans[ptr]=low.first+y+x, par[ptr]=low.second;
} else {
ans[ptr]=up.first-y+x, par[ptr]=up.second;
} assert(ans[ptr] <= INF);
upd(1, 1, sz, sc[y], 0, {ans[ptr]-y-x, ptr});
upd(1, 1, sz, sc[y], 1, {ans[ptr]+y-x, ptr});
++ptr;
}
for (auto &u : bg[x]) {
if (u.second < u.first) swap(u.first, u.second);
clear(1, 1, sz, sc[u.first], sc[u.second]);
}
}
int idx=0;
for (auto u : p) {
if (u.first == x && u.second == y) break;
else ++idx;
}
cout<<ans[idx]<<"\n";
vector<pii> mv;
int pr=idx;
while (par[pr] != -1) {
int x=p[pr].first, y=p[pr].second;
if (p[par[pr]].second != y) mv.push_back({0, y-p[par[pr]].second});
if (p[par[pr]].first != x) mv.push_back({x-p[par[pr]].first, 0});
pr=par[pr];
} assert((int)mv.size() <= h);
reverse(mv.begin(), mv.end());
cout<<mv.size()<<"\n";
for (auto u : mv) cout<<u.first<<" "<<u.second<<"\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
36308 KB |
Extra information in the output file |
| 2 |
Correct |
19 ms |
36424 KB |
Output is correct |
| 3 |
Correct |
20 ms |
36456 KB |
Output is correct |
| 4 |
Partially correct |
25 ms |
37380 KB |
Partially correct (80% score). Path intersects a building. |
| 5 |
Incorrect |
592 ms |
61928 KB |
Extra information in the output file |
| 6 |
Partially correct |
243 ms |
51448 KB |
Partially correct (80% score). Path intersects a building. |
| 7 |
Partially correct |
338 ms |
43236 KB |
Partially correct (80% score). Path intersects a building. |
| 8 |
Incorrect |
715 ms |
49424 KB |
Extra information in the output file |
| 9 |
Partially correct |
499 ms |
45584 KB |
Partially correct (80% score). Path is not of advertised length! |
| 10 |
Incorrect |
529 ms |
45848 KB |
Extra information in the output file |
