Language: C++

#include<bits/stdc++.h>  // Rooks, by Errichto
using namespace std;
#define sim template < class c
#define ris return  this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge range(c i, c j) { return rge{i, j}; }
sim > auto dud(c x) -> decltype(cerr << x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge d) {
  this << "[";
  for (auto it = d.b; it != d.e; ++it)
    this << ", " + 2  (it == d.b) << it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #VA_ARGS ": " << (VA_ARGS) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

struct Rook {
    int x, y, id;
    bool operator <(const Rook& other) const {
        return x < other.x;
    }
};
long long hack;
int main() {
    int n;
    scanf("%d", &n);
    assert(2 <= n && n <= 200  1000);
    vector rooks(n);
    for(int i = 0; i < n; ++i) {
        rooks[i].id = i;
        scanf("%d%d", &rooks[i].x, &rooks[i].y);
        assert(1 <= min(rooks[i].x, rooks[i].y) && max(rooks[i].x, rooks[i].y) <= 1000  1000);
    }
    sort(rooks.begin(), rooks.end());
    vector ys{INT_MIN, INT_MAX}; // two sentinels for convenience
    for(int i = 0; i < n; ++i) {
        ys.push_back(rooks[i].y);
    }
    sort(ys.begin(), ys.end());
    for(int i = 0; i < n - 1; ++i) {
        assert(ys[i] != ys[i+1]);
        assert(rooks[i].x != rooks[i+1].x);
    }
    vector> answer(n, {-1, -1});
    for(int start = 0; start < n; ++start) {
        if(answer[rooks[start].id].first != -1) {
            continue;
        }

        int start_y = lower_bound(ys.begin(), ys.end(), rooks[start].y) - ys.begin();
        int y1 = start_y - 1, y2 = start_y + 1;

        int L = start, R = start;
        int prev_dir = -1;
        vector> intervals;
        while(true) {
            bool found = false;
            for(int i : {L - 1, R + 1}) {
                if(0 <= i && i < n) {
                    bool prev_y = (ys[y1] == rooks[i].y);
                    bool next_y = (ys[y2] == rooks[i].y);
                    if(prev_y || next_y) {
                        int direction = (prev_y == (i == L - 1)); // 0 or 1
                        // debug() << imie(start) imie(i) imie(direction);
                        if(prev_dir == -1) {
                            prev_dir = direction;
                        }
                        if(prev_dir != direction) {
                            intervals.emplace_back(L, R);
                            prev_dir = direction;
                        }
                        prev_y ? y1-- : y2++;
                        i == L-1 ? L-- : R++;
                        found = true;
                        break;
                    }
                }
            }
            if(!found) {
                break;
            }
        }
        if(intervals.empty() || intervals.back() != make_pair(L, R)) {
            intervals.emplace_back(L, R);
        }
        const int s = intervals.size();
        debug() << imie(start) imie(intervals);

        { // complexity check
            static int sum_s = 0, sum_len = 0;
            if(s > 1) sum_s += s;
            assert(sum_s <= n);
            sum_len += R - L + 1;
            assert(sum_len <= 3  n); // N + out + 2  border    ('out' and 'border' are disjoint)
            static vector basic(n), out(n), border(n);
            pair i_basic = intervals[0], i_out = intervals[max(0,s-2)], i_border = intervals.back();
            for(int i = i_border.first; i <= i_border.second; ++i) {
                if(i_basic.first <= i && i <= i_basic.second) {
                    assert(++basic[i] == 1);
                }
                else if(i_out.first <= i && i <= i_out.second) {
                    assert(++out[i] == 1 && border[i] == 0);
                }
                else {
                    assert(++border[i] <= 2 && out[i] == 0);
                }
            }
        }

        const long long INF = 1e18L + 5;
        auto min_self = & {
            a = min(a, b);
        };
        auto f = & { // manhattan distance between two rooks
            return abs(rooks[i].x - rooks[j].x) + abs(rooks[i].y - rooks[j].y);
        };
        vector> dp(s, vector(2, INF));
        // dp[i][0] is minimum number of REMAINING operations if we did interval i and we are at its left end
        // dp[i][1] -- same but right end
        dp[s-1][0] = dp[s-1][1] = 0;
        for(int who = s - 1; who >= 1; --who) {
            // [L1, [L2, R1], R2]
            int L1 = intervals[who].first;
            int L2 = intervals[who-1].first;
            int R1 = intervals[who-1].second;
            int R2 = intervals[who].second;
            hack += (long long) (L2 - L1)  (R2 - R1);
            min_self(dp[who-1][0], dp[who][0] + (R1 == R2 ? f(L1, L2) : f(L1, R2) + f(R2, L2)));
            min_self(dp[who-1][1], dp[who][0] + f(L1, R2) + f(R2, R1));
            min_self(dp[who-1][0], dp[who][1] + f(R2, L1) + f(L1, L2));
            min_self(dp[who-1][1], dp[who][1] + (L1 == L2 ? f(R1, R2) : f(R2, L1) + f(L1, R1)));
        }
        int low = intervals[0].first, high = intervals[0].second;
        for(int i = low; i <= high; ++i) {
            assert(answer[rooks[i].id] == make_pair(-1, -1LL));
            answer[rooks[i].id] = {
                R - L,
                min(dp[0][0] + f(low, high) + f(high, i), dp[0][1] + f(high, low) + f(low, i))
            };
        }
    }
    for(pair p : answer) {
        // printf("%d %lld\n", p.first, p.second - p.first);
        printf("%lld\n", p.second - p.first);
    }
    cerr << "hack = " << hack << endl;
}

Compiler output:
a.cc:30:17: error: '#' is not followed by a macro parameter
   30 | #define imie(...) " [" << #VA_ARGS ": " << (VA_ARGS) << "] "
      |                 ^
a.cc:9:7: error: deduced class type 'rge' in function return type
    9 | sim > rge range(c i, c j) { return rge{i, j}; }
      |       ^~~
a.cc:8:14: note: 'template<class c> struct rge' declared here
    8 | sim > struct rge { c b, e; };
      |              ^~~
a.cc: In member function 'debug& debug::operator<<(const c&)':
a.cc:4:21: error: invalid initialization of non-const reference of type 'debug&' from an rvalue of type 'debug*'
    4 | #define ris return  this
      |                     ^~~~
a.cc:27:21: note: in expansion of macro 'ris'
   27 | sim dor(const c&) { ris; }
      |                     ^~~
In file included from /usr/include/c++/14/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:106,
                 from a.cc:1:
a.cc: In function 'int main()':
a.cc:43:32: error: expected ')' before numeric constant
   43 |     assert(2 <= n && n <= 200  1000);
      |                                ^~~~
a.cc:43:32: error: expected ')' before numeric constant
a.cc:43:5: note: to match this '('
   43 |     assert(2 <= n && n <= 200  1000);
      |     ^~~~~~
a.cc:44:19: error: class template argument deduction failed:
   44 |     vector rooks(n);
      |                   ^
a.cc:44:19: error: no matching function for call to 'vector(int&)'
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53:
/usr/include/c++/14/bits/stl_vector.h:707:9: note: candidate: 'template<class _Tp, class _Alloc, class _InputIterator, class> vector(_InputIterator, _InputIterator, const _Alloc&)-> std::vector<_Tp, _Alloc>'
  707 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:707:9: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:678:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::initializer_list<_Tp>, const _Alloc&)-> std::vector<_Tp, _Alloc>'
  678 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:678:7: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:659:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::vector<_Tp, _Alloc>&&, std::__type_identity_t<_Alloc>&)-> std::vector<_Tp, _Alloc>'
  659 |       vector(vector&& __rv, const __type_identity_t<allocator_type>& __m)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:659:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:640:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::vector<_Tp, _Alloc>&&, const _Alloc&, std::false_type)-> std::vector<_Tp, _Alloc>'
  640 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:640:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:635:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::vector<_Tp, _Alloc>&&, const _Alloc&, std::true_type)-> std::vector<_Tp, _Alloc>'
  635 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:635:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:624:7: note: candidate: 'template<class _Tp, class _Alloc> vector(const std::vector<_Tp, _Alloc>&, std::__type_identity_t<_Alloc>&)-> std::vector<_Tp, _Alloc>'
  624 |       vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:624:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:620:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::vector<_Tp, _Alloc>&&)-> std::vector<_Tp, _Alloc>'
  620 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:620:7: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   mismatched types 'std::vector<_Tp, _Alloc>' and 'int'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:601:7: note: candidate: 'template<class _Tp, class _Alloc> vector(const std::vector<_Tp, _Alloc>&)-> std::vector<_Tp, _Alloc>'
  601 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:601:7: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   mismatched types 'const std::vector<_Tp, _Alloc>' and 'int'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:569:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::size_t, const _Tp&, const _Alloc&)-> std::vector<_Tp, _Alloc>'
  569 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:569:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:556:7: note: candidate: 'template<class _Tp, class _Alloc> vector(std::size_t, const _Alloc&)-> std::vector<_Tp, _Alloc>'
  556 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:556:7: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   couldn't deduce template parameter '_Tp'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:542:7: note: candidate: 'template<class _Tp, class _Alloc> vector(const _Alloc&)-> std::vector<_Tp, _Alloc>'
  542 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:542:7: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   couldn't deduce template parameter '_Tp'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:531:7: note: candidate: 'template<class _Tp, class _Alloc> vector()-> std::vector<_Tp, _Alloc>'
  531 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:531:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:428:11: note: candidate: 'template<class _Tp, class _Alloc> vector(std::vector<_Tp, _Alloc>)-> std::vector<_Tp, _Alloc>'
  428 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:428:11: note:   template argument deduction/substitution failed:
a.cc:44:19: note:   mismatched types 'std::vector<_Tp, _Alloc>' and 'int'
   44 |     vector rooks(n);
      |                   ^
/usr/include/c++/14/bits/stl_vector.h:2033:5: note: candidate: 'template<class _InputIterator, class _ValT, class _Allocator, class, class> std::vector(_InputIterator, _InputIterator, _Allocator)-> vector<_ValT, _Allocator>'
 2033 |     vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
      |     ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:2033:5: note:   candidate expects 2 arguments, 1 provided
a.cc:48:89: error: expected ')' before numeric constant
   48 |         assert(1 <= min(rooks[i].x, rooks[i].y) && max(rooks[i].x, rooks[i].y) <= 1000  1000);
      |                                                                                         ^~~~
a.cc:48:89: error: expected ')' before numeric constant
a.cc:48:9: note: to match this '('
   48 |         assert(1 <= min(rooks[i].x, rooks[i].y) && max(rooks[i].x, rooks[i].y) <= 1000  1000);
      |         ^~~~~~
a.cc:60:11: error: expected unqualified-id before '>' token
   60 |     vector> answer(n, {-1, -1});
      |           ^
a.cc:60:31: error: expected primary-expression before ')' token
   60 |     vector> answer(n, {-1, -1});
      |                               ^
a.cc:62:12: error: 'answer' was not declared in this scope
   62 |         if(answer[rooks[start].id].first != -1) {
      |            ^~~~~~
a.cc:71:15: error: expected unqualified-id before '>' token
   71 |         vector> intervals;
      |               ^
a.cc:85:29: error: 'intervals' was not declared in this scope
   85 |                             intervals.emplace_back(L, R);
      |                             ^~~~~~~~~
a.cc:99:12: error: 'intervals' was not declared in this scope
   99 |         if(intervals.empty() || intervals.back() != make_pair(L, R)) {
      |            ^~~~~~~~~
a.cc:102:23: error: 'intervals' was not declared in this scope
  102 |         const int s = intervals.size();
      |                       ^~~~~~~~~
a.cc:103:20: error: 'imie' was not declared in this scope
  103 |         debug() << imie(start) imie(intervals);
      |                    ^~~~
a.cc:110:34: error: expected ')' before 'n'
  110 |             assert(sum_len <= 3  n); // N + out + 2  border    ('out' and 'border' are disjoint)
      |                                  ^
a.cc:110:34: error: expected ')' before 'n'
a.cc:110:13: note: to match this '('
  110 |             assert(sum_len <= 3  n); // N + out + 2  border    ('out' and 'border' are disjoint)
      |             ^~~~~~
a.cc:111:34: error: class template argument deduction failed:
  111 |             static vector basic(n), out(n), border(n);
      |                                  ^
a.cc:111:34: error: no matching function for call to 'vector(int&)'
/usr/include/c++/14/bits/stl_vector.h:707:9: note: candidate: 'template<class _Tp, class _Alloc, class _InputIterator, class> vector(_InputIterator, _InputIterator, const _Alloc&)-> std::vector<_Tp, _Alloc>'
  707 |         vector(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:707:9: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_vector.h:678:7: note: candidate: 'templ