Submission #1118813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1118813	2024-11-26T08:01:22 Z	PVSekhar	Walk (CEOI06_walk)	C++14	100 / 100	103 ms	8260 KB

walk

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 1e6 + 10;
const ll INF = 1e12 + 10;

struct Pt{
    int x, y, ind;
    Pt(const int x_ = 0, const int y_ = 0, const int ind_ = 0) : x(x_), y(y_), ind(ind_) {}

    friend bool operator<(const Pt &a, const Pt &b) {
        return a.ind != b.ind && (a.x < b.x || (a.x == b.x && a.y < b.y));
    }

    friend bool operator==(const Pt &a, const Pt &b) {
        return a.ind == b.ind;
    }

    friend bool operator!=(const Pt &a, const Pt &b) {
        return a.ind != b.ind;
    }

    friend std::ostream& operator<<(std::ostream &os, const Pt &p) {
        os << "(" << p.x << ", " << p.y - N << ", " << p.ind << ")";
        return os;
    }
};

vector<Pt> pts;
int ind[2 * N], par[N];
ll dist[N];
set<int> store;

void add(int p_ind) {
    if (store.find(pts[p_ind].y) != store.end()) {
        dist[p_ind] = dist[ind[pts[p_ind].y]];
        par[p_ind] = ind[pts[p_ind].y];
        ind[pts[p_ind].y] = p_ind;
        return;
    }
    store.insert(pts[p_ind].y);
    auto it = store.find(pts[p_ind].y);
    ind[pts[p_ind].y] = p_ind;
    if (it != store.begin()) {
        it--;
        dist[p_ind] = dist[ind[*it]] + abs(pts[p_ind].y - pts[ind[*it]].y);
        par[p_ind] = ind[*it];
        it++;
    }
    ll temp;
    if ((++it) != store.end()) {
        temp = dist[ind[*it]] + abs(pts[p_ind].y - pts[ind[*it]].y);
        if (dist[p_ind] > temp) {
            dist[p_ind] = temp;
            par[p_ind] = ind[*it];
        }
    }
}

void add_rec(int &p_ind) {
    add(p_ind);
    add(p_ind + 1);
    auto it = store.find(pts[p_ind + 1].y);
    vector<int> to_r;
    while ((it--) != store.begin() && *it > pts[p_ind].y) to_r.push_back(*it);
    for (int x : to_r) store.erase(x);
}

void solve() {
    int x, y, x1, y1, x2, y2, n;
    cin >> x >> y >> n;
    y += N;
    pts.push_back(Pt(-1, N, 0));
    for (int i = 1; i <= n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x) continue;
        y1 += N;
        y2 += N;
        pts.push_back(Pt(x1 - 1, y1 - 1, 2 * i));
        pts.push_back(Pt(x1 - 1, y2 + 1, 2 * i + 1));
    }
    pts.push_back(Pt(x, y, n));
    sort(pts.begin(), pts.end());
    pts[0].x = 0;
    n = pts.size();
    for (int i = 1; i < n; i++) dist[i] = INF;
    for (int i = 0; i < n; i++) pts[i].ind = i;
    store.insert(N);
    dist[0] = 0;
    ind[N] = 0;
    for (int i = 1; i < n - 1; i += 2) add_rec(i);
    add(n - 1);
    cout << dist[n - 1] + x << "\n";
    vector<int> path;
    vector<pair<int, int>> ans;
    int cur = n - 1, last = -1;
    path.push_back(cur);
    while (cur) path.push_back(cur = par[cur]);
    reverse(path.begin(), path.end());
    Pt p = pts[path[0]], q = pts[path[1]];
    if (p.x != q.x) ans.push_back(make_pair(q.x - p.x, 0)), last = 0;
    if (p.y != q.y) ans.push_back(make_pair(0, q.y - p.y)), last = 1;
    for (int i = 2; i < path.size(); i++) {
        p = pts[path[i - 1]], q = pts[path[i]];
        if (last == -1) {
            if (p.x != q.x) ans.push_back(make_pair(q.x - p.x, 0)), last = 0;
            if (p.y != q.y) ans.push_back(make_pair(0, q.y - p.y)), last = 1;
        } else if (last == 1) {
            if (p.x == q.x) ans.back().second += q.y - p.y;
            else {
                if (p.x != q.x) ans.push_back(make_pair(q.x - p.x, 0)), last = 0;
                if (p.y != q.y) ans.push_back(make_pair(0, q.y - p.y)), last = 1;
            }
        } else {
            if (p.y == q.y) ans.back().first += q.x - p.x;
            else {
                if (p.x != q.x) ans.push_back(make_pair(q.x - p.x, 0)), last = 0;
                if (p.y != q.y) ans.push_back(make_pair(0, q.y - p.y)), last = 1;
            }
        }
    }
    cout << ans.size() << "\n";
    for (auto it : ans) {
        cout << it.first << " " << it.second << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Compilation message

walk.cpp: In function 'void solve()':
walk.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 2; i < path.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	3 ms	488 KB	Output is correct
5	Correct	91 ms	7892 KB	Output is correct
6	Correct	32 ms	4540 KB	Output is correct
7	Correct	58 ms	4028 KB	Output is correct
8	Correct	103 ms	6068 KB	Output is correct
9	Correct	80 ms	8100 KB	Output is correct
10	Correct	85 ms	8260 KB	Output is correct