#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10, maxc = 10000; /// fix this
struct point
{
int x, y;
void read()
{
cin >> x >> y;
}
point(int _x = 0, int _y = 0)
{
x = _x;
y = _y;
}
};
struct rectangle
{
point A, B;
void read()
{
A.read();
B.read();
}
} r[maxn];
struct line
{
int x, en;
int type;
int idx;
line(int _x, int _type, int _idx)
{
type = _type;
x = _x;
idx = _idx;
}
bool operator < (const line &l) const
{
if (x == l.x)
return type > l.type;
return x < l.x;
}
};
int st_x, st_y, n;
vector < pair < int, int > > adj[maxn * 2];
void read()
{
cin >> st_x >> st_y >> n;
for (int i = 1; i <= n; i ++)
{
r[i].A.read();
r[i].B.read();
if (r[i].A.x > r[i].B.x)
swap(r[i].A.x, r[i].B.x);
if (r[i].A.y > r[i].B.y)
swap(r[i].A.y, r[i].B.y);
r[i].A.y += maxc;
r[i].B.y += maxc;
}
st_y += maxc;
}
stack < int > tree[8 * maxc];
int sum[8 * maxc];
int get_index(int root, int left, int right, int qleft, int qright)
{
//cout << root << " :: " << left << " :: " << right << endl;
if (sum[root] == 0)
return -1;
if (left > qright || right < qleft)
return -1;
if (left == right)
{
return left;
}
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (sum[root * 2] > 0)
return get_index(root * 2, left, mid, qleft, qright);
return get_index(root * 2 + 1, mid + 1, right, qleft, qright);
}
/// int mid = (left + right) / 2;
return max(get_index(root * 2, left, mid, qleft, qright),
get_index(root * 2 + 1, mid + 1, right, qleft, qright));
}
int update(int root, int left, int right, int pos, int val)
{
if (left == right)
{
int to = 0;
if (val == -1)
{
to = tree[root].top();
tree[root].pop(), sum[root] --;
}
else
{
to = -1;
tree[root].push(val), sum[root] ++;
}
return to;
}
int mid = (left + right) / 2, ans;
if (pos <= mid)
ans = update(root * 2, left, mid, pos, val);
else
ans = update(root * 2 + 1, mid + 1, right, pos, val);
sum[root] = sum[root * 2] + sum[root * 2 + 1];
return ans;
}
pair < int, int > get_point(int v)
{
if (v == 0)
return {0, maxc};
if (v <= n)
{
return {r[v].B.x, r[v].A.y - 1};
}
if (v > n)
{
v -= n;
return {r[v].B.x, r[v].B.y + 1};
}
}
int distance_to_end(int idx)
{
pair < int, int > p = get_point(idx);
return abs(st_x - p.first) + abs(st_y - p.second);
if (idx == 0)
{
return st_x;
}
if (idx <= n)
{
int x = r[idx].B.x, y = r[idx].A.y - 1;
///cout << x << " : " << y << " : " << st_x << " : " << st_y << endl;
return abs(x - st_x) + abs(y - st_y);
}
if (idx > n)
{
idx -= n;
int x = r[idx].B.x, y = r[idx].B.y + 1;
return abs(x - st_x) + abs(y - st_y);
}
}
int get_distance(int v, int u)
{
pair < int, int > s = get_point(v);
pair < int, int > t = get_point(u);
return abs(s.first - t.first) + abs(s.second - t.second);
}
int used[2 * maxn], dp[2 * maxn];
void dfs(int v)
{
used[v] = 1;
///cout << v << endl;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (!used[u])
dfs(u);
dp[v] = min(dp[v], dp[u] + nb.second);
}
}
stack < int > ps[2 * maxc];
void sweep_line()
{
vector < line > event;
for (int i = 1; i <= n; i ++)
{
event.push_back(line(r[i].A.x, 1, i));
}
event.push_back(line(st_x, 2, -1));
sort(event.begin(), event.end());
for (int i = 0; i <= 2 * n; i ++)
dp[i] = 1e9;
int lb = 0, rb = 2 * maxc - 1;
update(1, lb, rb, maxc, 0);
ps[maxc].push(0);
for (int i = 0; i < event.size(); i ++)
{
line cur = event[i];
int idx = cur.idx;
///cout << "event " << cur.x << endl;
///cout << "size " << ps[1000].size() << endl;
if (cur.type == 2)
{
/**for (int j = 0; j < 2 * maxc; j ++)
{
while(!ps[j].empty())
{
int ver = ps[j].top();
ps[j].pop();
dp[ver] = distance_to_end(ver);
///cout << ver << endl;
}
}*/
///break;
while(true)
{
int pos = get_index(1, lb, rb, lb, rb);
if (pos == -1)
break;
int ver = update(1, lb, rb, pos, -1);
dp[ver] = distance_to_end(ver);
///cout << "dp " << dp[ver] << " " << ver << endl;
///adj[ver].push_back(idx);
///adj[ver].push_back(idx + n);
}
break;
}
/**for (int j = r[idx].A.y; j <= r[idx].B.y; j ++)
{
while(!ps[j].empty())
{
int ver = ps[j].top();
ps[j].pop();
///cout << "type bad " << ver << " " << idx << endl;
adj[ver].push_back({idx, get_distance(ver, idx)});
adj[ver].push_back({idx + n, get_distance(ver, idx + n)});
}
}*/
while(true)
{
int pos = get_index(1, lb, rb, r[idx].A.y, r[idx].B.y);
if (pos == -1)
break;
int ver = update(1, lb, rb, pos, -1);
//cout << "type good " << ver << " : " << idx << endl;
//cout << r[idx].A.y << " range " << r[idx].B.y << endl;
//cout << ver << " : " << idx + n << endl;
adj[ver].push_back({idx, get_distance(ver, idx)});
adj[ver].push_back({idx + n, get_distance(ver, idx + n)});
//cout << adj[ver].back().second << endl;
}
///cout << "-------------" << endl;
//ps[r[idx].A.y - 1].push(idx);
//ps[r[idx].B.y - 1].push(idx + n);
update(1, lb, rb, r[idx].A.y - 1, idx);
update(1, lb, rb, r[idx].B.y - 1, idx + n);
///cout << "add " << idx << " " << idx + n << " " << r[idx].B.y + 1 << endl;
}
}
void solve()
{
read();
sweep_line();
dfs(0);
cout << dp[0] << endl;
}
int main()
{
///freopen("test.txt", "r", stdin);
solve();
return 0;
}
/**
10 2
2
1 -1
3 3
5 -1
8 3
*/
Compilation message
walk.cpp: In function 'void sweep_line()':
walk.cpp:220:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for (int i = 0; i < event.size(); i ++)
| ~~^~~~~~~~~~~~~~
walk.cpp: In function 'std::pair<int, int> get_point(int)':
walk.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
156 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
39 ms |
73896 KB |
Unexpected end of file - token expected |
| 2 |
Incorrect |
38 ms |
73932 KB |
Unexpected end of file - token expected |
| 3 |
Incorrect |
37 ms |
74076 KB |
Found length 167982, official output says 160150. |
| 4 |
Incorrect |
40 ms |
74124 KB |
Found length 139594, official output says 126772. |
| 5 |
Incorrect |
177 ms |
81280 KB |
Found length 262643, official output says 175579. |
| 6 |
Incorrect |
86 ms |
76616 KB |
Found length 178498, official output says 218042. |
| 7 |
Incorrect |
147 ms |
78216 KB |
Found length 109255, official output says 109253. |
| 8 |
Incorrect |
228 ms |
81012 KB |
Found length 16355, official output says 16349. |
| 9 |
Incorrect |
230 ms |
82308 KB |
Found length 215995, official output says 217249. |
| 10 |
Incorrect |
230 ms |
82428 KB |
Found length 195029, official output says 196657. |
