Submission #714936

#TimeUsernameProblemLanguageResultExecution timeMemory
714936mbfibatWalk (CEOI06_walk)C++17
0 / 100
166 ms13492 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; int seg[8000011], lazy[8000011]; void diffuse(int node, int l, int r) { if (lazy[node]) { seg[node] = lazy[node]; if (l != r) { lazy[node * 2] = lazy[node]; lazy[node * 2 + 1] = lazy[node]; } lazy[node] = 0; } } void update(int node, int l, int r, int L, int R, int val) { diffuse(node, l, r); if (r < L || R < l) return; if (L <= l && r <= R) { lazy[node] = val; diffuse(node, l, r); return; } int mi = (l + r) / 2; update(node * 2, l, mi, L, R, val); update(node * 2 + 1, mi + 1, r, L, R, val); seg[node] = max(seg[node * 2], seg[node * 2 + 1]); // Not needed because only query point lmao } int query(int node, int l, int r, int p) { diffuse(node, l, r); if (p < l || r < p) return 0; if (p == l && l == r) return seg[node]; int mi = (l + r) / 2; int lhs = query(node * 2, l, mi, p); int rhs = query(node * 2 + 1, mi + 1, r, p); return max(lhs, rhs); } struct Point { int x, y, id, t; Point(){} Point(int x, int y) : x(x), y(y) {} Point(int x, int y, int id, int t) : x(x), y(y), id(id), t(t) {} bool operator<(Point& other) { return x < other.x; } }; struct Event { int x, y1, y2, v; Event(){} Event(int x, int y1, int y2, int v) : x(x), y1(y1), y2(y2), v(v) {} bool operator<(Event& other) { return x < other.x; } }; int X, Y; int n; ii mat[2][1000001]; int val[2][1000001]; int nxt_point[1000001]; int pos_in_p[2][1000001]; int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> X >> Y >> n; vector<Point> p; vector<Event> e; p.emplace_back(X, Y, 0, 0); for (int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; p.emplace_back(x2 + 1, y1 - 1, i, 0); p.emplace_back(x2 + 1, y2 + 1, i, 1); e.emplace_back(x1, y1, y2, i); mat[0][i] = ii(x2 + 1, y1 - 1); mat[1][i] = ii(x2 + 1, y2 + 1); } sort(p.begin(), p.end()); sort(e.begin(), e.end()); for (int i = 0; i < p.size(); i++) pos_in_p[p[i].t][p[i].id] = i; int pos_p = 0, pos_e = 0; for (int x = 1; x <= 1000000; x++) { while (pos_e < e.size() && e[pos_e].x == x) { // cerr << '!' << e[pos_e].y1 << ' ' << e[pos_e].y2 << ' ' << e[pos_e].v << '\n'; update(1, 0, 2000000, e[pos_e].y1 + 1000000, e[pos_e].y2 + 1000000, e[pos_e].v); ++pos_e; } while (pos_p < p.size() && p[pos_p].x == x) { int nxt = query(1, 0, 2000000, p[pos_p].y + 1000000); // cerr << '!' << pos_p << ' ' << p[pos_p].x << ' ' << p[pos_p].y << ' ' << nxt << '\n'; if (!nxt) { val[p[pos_p].t][p[pos_p].id] = abs(p[pos_p].y); nxt_point[pos_p] = -1; } else { int d = val[0][nxt] + abs(mat[0][nxt].second - p[pos_p].y); int u = val[1][nxt] + abs(mat[1][nxt].second - p[pos_p].y); val[p[pos_p].t][p[pos_p].id] = min(u, d); if (d < u) nxt_point[pos_p] = pos_in_p[0][nxt]; else nxt_point[pos_p] = pos_in_p[1][nxt]; } ++pos_p; } } int ans = val[0][0]; vector<ii> path; for (int i = 0; i < p.size(); i++) { if (p[i].x == X && p[i].y == Y) { // find path int cur = i; while (1) { int nxt = nxt_point[cur]; // cerr << '?' << p[cur].x << ' ' << p[cur].y << '\n'; // cerr << cur << ' ' << nxt << '\n'; if (nxt == -1) { if (p[cur].x) path.emplace_back(p[cur].x, 0); if (p[cur].y) path.emplace_back(0, p[cur].y); break; } if (p[cur].x - p[nxt].x) path.emplace_back(p[cur].x - p[nxt].x, 0); if (p[cur].y - p[nxt].y) path.emplace_back(0, p[cur].y - p[nxt].y); cur = nxt; } break; } } reverse(path.begin(), path.end()); cout << ans << '\n'; cout << path.size() << '\n'; for (auto& [dx, dy] : path) cout << dx << ' ' << dy << '\n'; }

Compilation message (stderr)

walk.cpp: In function 'int main(int, char**)':
walk.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   while (pos_e < e.size() && e[pos_e].x == x) {
      |          ~~~~~~^~~~~~~~~~
walk.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   while (pos_p < p.size() && p[pos_p].x == x) {
      |          ~~~~~~^~~~~~~~~~
walk.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...