| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 412747 |
2021-05-27T12:45:07 Z |
pure_mem |
Walk (CEOI06_walk) |
C++14 |
|
150 ms |
12208 KB |
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define double long double
using namespace std;
const int N = 1e5 + 12, INF = 1e6 + 2;
int cf(int x, int y);
struct node{
int p = 0;
node* to[2] = {nullptr, nullptr};
node* getp(int v){
if(to[v] == nullptr) to[v] = new node();
return to[v];
}
void upd(int tl, int tr, int l, int r, int val){
if(tl > r || l > tr) return;
if(tl >= l && tr <= r) return void(p = val);
int tm = (tl + tr) / 2;
if((tl + tr) % 2 == -1) tm -= 1;
getp(0)->upd(tl, tm, l, r, val);
getp(1)->upd(tm + 1, tr, l, r, val);
}
int get(int tl, int tr, int pos){
if(tl == tr) return p;
int tm = (tl + tr) / 2;
if((tl + tr) % 2 == -1) tm -= 1;
int val;
if(pos <= tm) val = (to[0] ? to[0]->get(tl, tm, pos): 0);
else val = (to[1] ? to[1]->get(tm + 1, tr, pos): 0);
return cf(val, p);
}
}root;
int n, nxt[2][N + 1], sx, sy, ans[2][N + 1];
pair< pair<int, int>, pair<int, int> > rect[N];
vector< pair< pair< int, int >, pair< int, int > > > g;
pair<int, int> dp[2][N + 1];
int cf(int x, int y){
if(y != 0 && (x == 0 || rect[x].X.Y < rect[y].X.Y)) return y;
return x;
}
void inputs(){
cin >> sx >> sy >> n;
g.push_back(MP(MP(sx, N), MP(sy, sy)));
for(int i = 1;i <= n;i++){
cin >> rect[i].X.X >> rect[i].Y.X >> rect[i].X.Y >> rect[i].Y.Y;
if(rect[i].X.X > rect[i].X.Y) swap(rect[i].X.X, rect[i].X.Y);
if(rect[i].Y.X > rect[i].Y.Y) swap(rect[i].Y.X, rect[i].Y.Y);
//sqX.push_back(rect[i].X.X), sqX.push_back(rect[i].X.Y);
g.push_back(MP(MP(rect[i].X.X, i), rect[i].Y));
g.push_back(MP(MP(rect[i].X.Y + 1, -i), rect[i].Y));
}
}
int getDist(pair<int, int> x, pair<int, int> y){
return abs(x.X - y.X) + abs(x.Y - y.Y);
}
void sweep(){
sort(g.begin(), g.end());
for(auto tmp: g){
if(tmp.X.Y > 0){
int z = (tmp.X.Y) != N;
// cerr << "1";
nxt[0][tmp.X.Y] = root.get(-INF, INF, tmp.Y.X - z);
// cerr << "2";
nxt[1][tmp.X.Y] = root.get(-INF, INF, tmp.Y.Y + z);
// cerr << "3";
if(z) root.upd(-INF, INF, tmp.Y.X, tmp.Y.Y, tmp.X.Y);
// cerr << "4\n";
}
}
for(auto tmp: g){
int id = tmp.X.Y;
if(id > 0 && id != N) continue;
if(id < 0) id = -id;
int z = (id != N);
if(!nxt[0][id])
dp[0][id] = MP(0, 0), ans[0][id] = getDist(MP(0, 0), MP(tmp.X.X, tmp.Y.X - z));
else {
int v0 = ans[0][nxt[0][id]] + getDist(MP(rect[nxt[0][id]].X.Y + 1, rect[nxt[0][id]].Y.X - 1), MP(tmp.X.X, tmp.Y.X - z));
int v1 = ans[1][nxt[0][id]] + getDist(MP(rect[nxt[0][id]].X.Y + 1, rect[nxt[0][id]].Y.Y + 1), MP(tmp.X.X, tmp.Y.X - z));
if(v0 < v1) dp[0][id] = MP(0, nxt[0][id]), ans[0][id] = v0;
else dp[0][id] = MP(1, nxt[0][id]), ans[0][id] = v1;
}
if(!nxt[1][id])
dp[1][id] = MP(0, 0), ans[1][id] = getDist(MP(0, 0), MP(tmp.X.X, tmp.Y.Y + z));
else {
int v0 = ans[0][nxt[1][id]] + getDist(MP(rect[nxt[1][id]].X.Y + 1, rect[nxt[1][id]].Y.X - 1), MP(tmp.X.X, tmp.Y.Y + z));
int v1 = ans[1][nxt[1][id]] + getDist(MP(rect[nxt[1][id]].X.Y + 1, rect[nxt[1][id]].Y.Y + 1), MP(tmp.X.X, tmp.Y.Y + z));
if(v0 < v1) dp[1][id] = MP(0, nxt[1][id]), ans[1][id] = v0;
else dp[1][id] = MP(1, nxt[1][id]), ans[1][id] = v1;
}
}
//cerr << ans[1][1] << "\n";
}
vector< pair<int, int> > out;
void rec(int x, int y){
if(y == 0) return;
pair<int, int> tmp = dp[x][y];
rec(tmp.X, tmp.Y);
pair<int, int> left = MP(0, 0), right = MP(sx, sy);
if(tmp.Y != 0) left = MP(rect[tmp.Y].X.Y + 1, tmp.X ? rect[tmp.Y].Y.Y + 1: rect[tmp.Y].Y.X - 1);
if(y != N) right = MP(rect[y].X.Y + 1, x ? rect[y].Y.Y + 1: rect[y].Y.X - 1);
if(left.Y != right.Y) out.push_back(MP(0, right.Y - left.Y));
if(left.X != right.X) out.push_back(MP(right.X - left.X, 0));
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
inputs();
sweep();
cout << ans[0][N] << "\n";
rec(0, N);
cout << out.size() << "\n";
for(pair<int, int> tmp: out){
cout << tmp.X << " " << tmp.Y << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
3 ms |
716 KB |
Output is correct |
| 5 |
Correct |
146 ms |
12208 KB |
Output is correct |
| 6 |
Correct |
48 ms |
5964 KB |
Output is correct |
| 7 |
Correct |
74 ms |
4832 KB |
Output is correct |
| 8 |
Correct |
150 ms |
9304 KB |
Output is correct |
| 9 |
Correct |
145 ms |
9908 KB |
Output is correct |
| 10 |
Correct |
133 ms |
10056 KB |
Output is correct |
