Submission #544143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544143	2022-04-01T08:09:11 Z	Sorting	Walk (CEOI06_walk)	C++17	100 / 100	160 ms	9656 KB

walk

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 2e6 + 17;
const int ADD = 1e6 + 3;
const ll INF = 1e18;

int x, y, n, mid[N];
array<int, 4> b[N];
vector<array<int, 3>> sweepline;

struct SegmentTree{
    pair<ll, ll> lp[4 * N];

    void push_lazy(int i, int l, int r){
        if(l == r) return;
        if(!lp[i].first && !lp[i].second) return;

        lp[2 * i + 1].second = lp[i].second;
        lp[2 * i + 2].second = lp[i].second;

        lp[2 * i + 1].first = lp[i].first;
        int mid = (l + r) >> 1;
        lp[2 * i + 2].first = lp[i].first + (mid + 1 - l) * lp[i].second;

        lp[i].first = 0;
        lp[i].second = 0;
    }
    void update(int sl, int sr, ll start, ll incr, int i = 0, int l = 0, int r = N - 1){
        push_lazy(i, l, r);
        if(sr < l || r < sl) return;
        if(sl <= l && r <= sr){
            lp[i].first = start + (l - sl) * incr;
            lp[i].second = incr;
            push_lazy(i, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(sl, sr, start, incr, 2 * i + 1, l, mid);
        update(sl, sr, start, incr, 2 * i + 2, mid + 1, r);
    }
    ll query(int s_idx, int i = 0, int l = 0, int r = N - 1){
        push_lazy(i, l, r);
        if(s_idx < l || r < s_idx) return 0;
        if(l == r) return lp[i].first;
        int mid = (l + r) >> 1;
        return query(s_idx, 2 * i + 1, l, mid) + query(s_idx, 2 * i + 2, mid + 1, r);
    }
} st;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> x >> y >> n;
    y += ADD;

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 4; ++j)
            cin >> b[i][j];
        b[i][1] += ADD;
        b[i][3] += ADD;

        if(b[i][1] > b[i][3])
            swap(b[i][1], b[i][3]);
        if(b[i][0] > b[i][2])
            swap(b[i][0], b[i][2]);

        sweepline.push_back({b[i][0], 1, i});
        sweepline.push_back({b[i][2], 2, i});;
    }

    sweepline.push_back({x, 0, y});

    sort(all(sweepline));

    st.update(0, ADD, ADD, -1);
    st.update(ADD, N - 1, 0, 1);

    int pr = 0;
    int i;
    for(i = 0; i < sweepline.size(); ++i){
        auto &e = sweepline[i];
        if(e[1] == 0){
            break;
        }

        auto [x, type, idx] = e;
        if(type == 1){
            st.update(b[idx][1], b[idx][3], INF, 0);
        }
        else{
            int l = st.query(b[idx][1] - 1);
            int r = st.query(b[idx][3] + 1);

            auto calc_mid = [](int l, int r, int sl, int sr){
                if(l <= r)
                    return (sl + (r - l) + sr) / 2;
                return (sl + sr - (l - r) + 1) / 2;
            };

            mid[idx] = calc_mid(l, r, b[idx][1] - 1, b[idx][3] + 1);
            if(b[idx][1] <= mid[idx])
                st.update(b[idx][1], mid[idx], l + 1, 1);
            if(mid[idx] + 1 <= b[idx][3]){
                int start = r - mid[idx] + b[idx][3];
                st.update(mid[idx] + 1, b[idx][3], start, -1);
            }
        }

        pr = x;
    }

    ll ans = st.query(y) + x;
    int curr_x = x, curr_y = y;
    vector<pair<int, int>> path;
    for(--i; i >= 0; --i){
        auto [x, type, idx] = sweepline[i];
        if(type == 1) continue;
        if(b[idx][1] <= curr_y && curr_y <= b[idx][3]){
            if(curr_x - x - 1 > 0)
                path.push_back({curr_x - x - 1, 0});
            
            int y;
            if(curr_y <= mid[idx])
                y = b[idx][1] - 1;
            else
                y = b[idx][3] + 1;

            path.push_back({0, curr_y - y});
            curr_y = y;
            curr_x = x + 1;
        }
    }
    if(curr_x)
        path.push_back({curr_x, 0});
    if(curr_y != ADD)
        path.push_back({0, curr_y - ADD});

    reverse(all(path));
    cout << ans << "\n";
    cout << path.size() << "\n";
    for(auto [dx, dy]: path)
        cout << dx << " " << dy << "\n"; 
}

Compilation message

walk.cpp: In function 'int main()':
walk.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(i = 0; i < sweepline.size(); ++i){
      |                ~~^~~~~~~~~~~~~~~~~~
walk.cpp:86:9: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
   86 |     int pr = 0;
      |         ^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	1748 KB	Output is correct
4	Correct	3 ms	1748 KB	Output is correct
5	Correct	144 ms	9348 KB	Output is correct
6	Correct	51 ms	6648 KB	Output is correct
7	Correct	78 ms	3260 KB	Output is correct
8	Correct	130 ms	5380 KB	Output is correct
9	Correct	160 ms	9656 KB	Output is correct
10	Correct	157 ms	8848 KB	Output is correct