| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 770202 |
2023-07-01T00:46:19 Z |
danikoynov |
Walk (CEOI06_walk) |
C++14 |
|
200 ms |
50068 KB |
#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 = 1000; /// 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[16 * maxc];
int sum[16 * maxc];
int get_index(int root, int left, int right, int qleft, int qright)
{
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;
}
int distance_to_end(int idx)
{
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);
}
}
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 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];
int dfs(int v)
{
used[v] = 1;
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);
}
}
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);
for (int i = 0; i < event.size(); i ++)
{
line cur = event[i];
int idx = cur.idx;
if (cur.type == 2)
{
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);
}
return;
}
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 << ver << " : " << idx << 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;
}
update(1, lb, rb, r[idx].A.y - 1, idx);
update(1, lb, rb, r[idx].B.y + 1, idx + n);
}
}
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 'int get_index(int, int, int, int, int)':
walk.cpp:93:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
93 | if (left == right)
| ^~
walk.cpp:96:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
96 | int mid = (left + right) / 2;
| ^~~
walk.cpp: In function 'int dfs(int)':
walk.cpp:194:1: warning: no return statement in function returning non-void [-Wreturn-type]
194 | }
| ^
walk.cpp: In function 'void sweep_line()':
walk.cpp:209:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | for (int i = 0; i < event.size(); i ++)
| ~~^~~~~~~~~~~~~~
walk.cpp: In function 'int distance_to_end(int)':
walk.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
156 | }
| ^
walk.cpp: In function 'std::pair<int, int> get_point(int)':
walk.cpp:173:1: warning: control reaches end of non-void function [-Wreturn-type]
173 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
35028 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
28 ms |
35016 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
24 ms |
34996 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
27 ms |
35128 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
139 ms |
48008 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
63 ms |
39512 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
96 ms |
42404 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
149 ms |
46352 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
196 ms |
49924 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
200 ms |
50068 KB |
Execution killed with signal 11 |
