| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 548628 |
2022-04-14T03:17:51 Z |
Evang |
Walk (CEOI06_walk) |
C++17 |
|
91 ms |
22012 KB |
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)
template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using pdb = pair<db, db>;
using pld = pair<ld, ld>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using vpdb = vc<pdb>;
using vpld = vc<pld>;
using str = string;
constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------
const int N = 1e5+5;
int n, dx, dy, a[N], b[N], c[N], d[N], nxt[N][2], g[N][4], ans;
struct segtree {
int size = 1<<21, tr[(1<<22)+100];
segtree() {
memset(tr, -1, sizeof tr);
}
void push(int i){
if(tr[i] == -1) return;
if(i < size) {
tr[2 * i] = tr[2 * i + 1] = tr[i];
tr[i] = -1;
}
}
void set(int l, int r, int i, int il, int ir, int x){
if(ir < l || r < il)
return;
if(l <= il && ir <= r){
tr[i] = x;
return;
}
push(i);
int im = (il+ir)/2;
set(l, r, 2*i, il, im, x);
set(l, r, 2*i+1, im+1, ir, x);
}
void set(int l, int r, int x){
set(l, r, 1, 0, size-1, x);
}
int get(int i){
int ans=-1;
i += size;
while(i>0){
if(tr[i] != -1)
ans = tr[i];
i /= 2;
}
return ans;
}
}seg;
vpi mov;
int dis(int x, int y, int x2, int y2){
return abs(x-x2) + abs(y-y2);
}
void evan2(int x, int y, int x2, int y2){
ans += abs(x-x2) + abs(y-y2);
if(x != x2)
mov.eb(x2-x, 0);
if(y!=y2)
mov.eb(0, y2-y);
assert(ssize(mov)<=int(1e6));
}
//void evan3(int x, int y, int j){
// if(j==-1){
// evan2(0, 1e6+1, x, y);
// return;
// }
//
// int option_down = g[j][2] + dis(c[j], b[j], x, y);
// int option_up = g[j][3] + dis(c[j], d[j], x, y);
// if(option_down < option_up){
// evan3(c[j], b[j], nxt[j][0]);
// evan2(c[j], b[j], x, y);
// }else{
// evan3(c[j], d[j], nxt[j][1]);
// evan2(c[j], d[j], x, y);
// }
//}
void evan(int i){
if(i==-1)
return;
int j = nxt[i][0];
if(j==-1)
g[i][0] = dis(0, 1e6+1, a[i], b[i]);
else{
evan(j);
g[i][0] = min(g[j][2] + dis(c[j], b[j], a[i], b[i]),
g[j][3] + dis(c[j], d[j], a[i], b[i]));
}
j = nxt[i][1];
if(j==-1)
g[i][1] = dis(0, 1e6+1, a[i], d[i]);
else{
if(nxt[i][0] != nxt[i][1])
evan(j);
g[i][1] = min(g[j][2] + dis(c[j], b[j], a[i], d[i]),
g[j][3] + dis(c[j], d[j], a[i], d[i]));
}
g[i][2] = dis(a[i], b[i], c[i], b[i]) + g[i][0];
g[i][3] = dis(c[i], d[i], a[i], d[i]) + g[i][1];
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("debug.txt", "w", stderr);
#else
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
#endif
cin >> dx >> dy >> n;
dy += 1e6+1;
vi cc;
vpi e{{dx, -1}};
for(int i = 0; i < n; ++i){
cin >> a[i] >> b[i] >> c[i] >> d[i];
if(a[i] > c[i])
swap(a[i], c[i]);
if(b[i] > d[i])
swap(b[i], d[i]);
e.eb(a[i], i);
--a[i];
--b[i];
++c[i];
++d[i];
b[i] += 1e6+1;
d[i] += 1e6+1;
}
sort(all(e));
int d_nxt = -1;
for(auto[x, i]: e){
if(i==-1){
d_nxt = seg.get(dy);
break;
}
nxt[i][0] = seg.get(b[i]);
nxt[i][1] = seg.get(d[i]);
seg.set(b[i]+1, d[i]-1, i);
int j = nxt[i][0];
if(j==-1)
g[i][0] = dis(0, 1e6+1, a[i], b[i]);
else{
// evan(j);
g[i][0] = min(g[j][2] + dis(c[j], b[j], a[i], b[i]),
g[j][3] + dis(c[j], d[j], a[i], b[i]));
}
j = nxt[i][1];
if(j==-1)
g[i][1] = dis(0, 1e6+1, a[i], d[i]);
else{
// if(nxt[i][0] != nxt[i][1])
// evan(j);
g[i][1] = min(g[j][2] + dis(c[j], b[j], a[i], d[i]),
g[j][3] + dis(c[j], d[j], a[i], d[i]));
}
g[i][2] = dis(a[i], b[i], c[i], b[i]) + g[i][0];
g[i][3] = dis(c[i], d[i], a[i], d[i]) + g[i][1];
}
// if(j !=-1)
// evan(j);
int x = dx, y = dy;
int j = d_nxt;
while(1){
if(j==-1) {
evan2(0, 1e6 + 1, x, y);
break;
}
int option_down = g[j][2] + dis(c[j], b[j], x, y);
int option_up = g[j][3] + dis(c[j], d[j], x, y);
if(option_down < option_up){
evan2(c[j], b[j], x, y);
tie(x, y, j) = mt(c[j], b[j], nxt[j][0]);
}else{
evan2(c[j], d[j], x, y);
tie(x, y, j) = mt(c[j], d[j], nxt[j][1]);
}
}
cout << ans << el;
cout << ssize(mov) << el;
reverse(all(mov));
for(auto[x, y]: mov)
cout << x << sp << y << el;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16724 KB |
Output is correct |
| 3 |
Correct |
7 ms |
16724 KB |
Output is correct |
| 4 |
Correct |
8 ms |
16724 KB |
Output is correct |
| 5 |
Correct |
73 ms |
21216 KB |
Output is correct |
| 6 |
Correct |
30 ms |
18264 KB |
Output is correct |
| 7 |
Correct |
43 ms |
19160 KB |
Output is correct |
| 8 |
Correct |
67 ms |
21504 KB |
Output is correct |
| 9 |
Correct |
91 ms |
22012 KB |
Output is correct |
| 10 |
Correct |
79 ms |
21968 KB |
Output is correct |
