Submission #414806

#	Time	Username	Problem	Language	Result	Execution time	Memory
414806		ja_kingy	Walk (CEOI06_walk)	C++17	40 / 100	431 ms	131072 KiB

walk

#include <bits/stdc++.h>
using namespace std;
 
const int mxX = 1e6+5;
int n, x, y, ncnt, rt[mxX];
typedef pair<int,int> pii;
vector<tuple<int,int,int,int>> boxes[mxX];
 
struct node{
    int lc, rc, lz;
    pii val;
} st[5000000];
 
int build(int l = -mxX, int r = mxX) {
    int t = ++ncnt;
    if (r - l > 1) {
        int m = (l+r)/2;
        st[t].lc = build(l, m);
        st[t].rc = build(m, r);
    }
    return t;
}
 
void push(int t) {
    if (st[t].lz) {
        st[++ncnt] = st[st[t].lc];
        st[t].lc = ncnt;
        st[++ncnt] = st[st[t].rc];
        st[t].rc = ncnt;
        st[st[t].lc].lz = st[st[t].rc].lz = 1;
        st[t].lz = 0;
        st[st[t].lc].val = st[st[t].rc].val = st[t].val;
    }
}
 
int upd(int ul, int ur, pii v, int t, int l = -mxX, int r = mxX) {
    if (ur <= l || r <= ul) return t;
    st[++ncnt] = st[t];
    t = ncnt;
    if (ul <= l && r <= ur) {
        st[t].lz = 1;
        st[t].val = v;
        return t;
    }
    push(t);
    int m = (l+r)/2;
    st[t].lc = upd(ul, ur, v, st[t].lc, l, m);
    st[t].rc = upd(ul, ur, v, st[t].rc, m, r);
    return t;
}
 
pii qry(int x, int t, int l = -mxX, int r = mxX) {
    if (r - l == 1) return st[t].val;
    push(t);
    int m = (l+r)/2;
    if (x < m) return qry(x, st[t].lc, l, m);
    else return qry(x, st[t].rc, m, r);
}
 
struct line{int pt, m, c;};
bool operator < (line a, line b) {
    return a.pt < b.pt;
}
set<line> lines;
 
int qd(int x) {
    auto l = lines.upper_bound({x,0,0});
    l--;
    return l->m * x + l->c;
}
 
int main() {
    cin >> x >> y >> n;
    rt[0] = build();
    lines.insert({-mxX,-1,0});
    lines.insert({0,1,0});
    for(int i = 0,x1,y1,x2,y2; i < n; ++i) {
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        boxes[x2+1].push_back({x1, y1, x2, y2});
    }
    for (int tx = 1; tx <= x; ++tx) {
        rt[tx] = rt[tx-1];
        for (auto [x1, y1, x2, y2] : boxes[tx]) {      
            int d1 = qd(y1-1), d2 = qd(y2+1), tp = (d2-d1+y2+y1)/2, tpd = d2+y2+1-tp, oldm = (--lines.upper_bound({y2+1,0,0}))->m;
            for (auto it = lines.lower_bound({y1-1,0,0}); it != lines.end() && it->pt <= y2+1;) {
                it = lines.erase(it);
            } 
            if (y1-1 != tp) lines.insert({y1-1, 1, d1 - (y1-1)});
            if (tp != y2+1) lines.insert({tp, -1, tpd + tp});
            lines.insert({y2+1, oldm, d2 - (y2+1)*oldm});
            rt[tx] = upd(y1, tp, {tx,y1-1}, rt[tx]);
            rt[tx] = upd(tp, y2+1, {tx,y2+1}, rt[tx]);
        }
    }
    vector<pii> pts, mvs;
    pii pt = {x,y};
    pts.push_back(pt);
    while (pt != make_pair(0,0)) {
        pt = qry(pt.second, rt[pt.first]);
        pts.push_back(pt);
    }
    reverse(pts.begin(), pts.end());
    for (int i = 0; i < pts.size()-1; ++i) {
        if (pts[i+1].second != pts[i].second) mvs.push_back({0,pts[i+1].second - pts[i].second});
        if (mvs.size() > 1 && mvs.back().first && mvs[mvs.size()-2].first) {
            int nw = mvs.back().first;
            mvs.pop_back();
            nw += mvs.back().first;
            mvs.pop_back();
            mvs.push_back({nw, 0});
        }
        if (mvs.size() > 1 && mvs.back().second && mvs[mvs.size()-2].second) {
            int nw = mvs.back().second;
            mvs.pop_back();
            nw += mvs.back().second;
            mvs.pop_back();
            mvs.push_back({0, nw});
        }
        if (pts[i+1].first != pts[i].first) mvs.push_back({pts[i+1].first - pts[i].first,0});
        if (mvs.size() > 1 && mvs.back().first && mvs[mvs.size()-2].first) {
            int nw = mvs.back().first;
            mvs.pop_back();
            nw += mvs.back().first;
            mvs.pop_back();
            mvs.push_back({nw, 0});
        }
        if (mvs.size() > 1 && mvs.back().second && mvs[mvs.size()-2].second) {
            int nw = mvs.back().second;
            mvs.pop_back();
            nw += mvs.back().second;
            mvs.pop_back();
            mvs.push_back({0, nw});
        }
    }
    cout << qd(y) + x << '\n';
    cout << mvs.size() << '\n';
    int zi = -1;
    for (pii m: mvs) {
        assert(m.first != 0 || m.second != 0);
        int nzi = m.first == 0 ? 1 : 2;
        assert(zi != nzi);
        zi = nzi;
        cout << m.first << ' ' << m.second << '\n';
    }
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100