Submission #1028012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028012		underwaterkillerwhale	Road Construction (JOI21_road_construction)	C++17	33 / 100	2749 ms	172760 KiB

road_construction

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e12;
const int BASE = 1337;

struct Coor {
    int x, y;
};

int n, K;
Coor a[N];

namespace sub4 {
    struct Data {
        int A, B;
        ll x;
    };
    struct Segment_Tree {
        int m;
        pair<ll,int> st[N << 2];

        void init (int n) {
            m = n;
            rep (i, 1, n << 2) st[i] = {INF, -1};
        }
        pair<ll, int> mer (pair<ll, int> A, pair<ll, int> B) {
            if (A.fs < B.fs) return A;
            return B;
        }
        void update (int id, int l, int r, int pos, pair<ll,int> val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                if (st[id].fs > val.fs) st[id] = val; /// >
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[id] = mer (st[id << 1], st[id << 1 | 1]);
        }
        pair<ll, int> get (int id,int l,int r, int u,int v) {
            if (l > v || r < u) return {INF, -1};
            if (l >= u && r <= v) return st[id];
            int mid = l + r >> 1;
            return mer(get (id << 1, l, mid, u, v), get(id << 1 | 1,mid + 1, r, u, v));
        }
        void update (int pos,pair<ll,int> val) {
            update (1, 1, m, pos, val);
        }
        pair<ll,int> get (int u, int v){
            return get(1, 1, m, u, v);
        }
    } ST1, ST2;


    struct cmp {
        bool operator () (Data A, Data B) { return A.x > B.x; }
    };

    int numY;
    vector<int> cY;
    bool dd[N];

    void compress () {
        rep (i, 1, n) cY.push_back(a[i].y);
        sort (ALL(cY));
        cY.resize(numY = unique(ALL(cY)) - cY.begin());
    }

    ll Dist (int A, int B) {
        return 1LL * abs(a[A].x - a[B].x) + abs(a[A].y - a[B].y);
    }

    void addtoset (priority_queue<Data, vector<Data>, cmp> &cur, int town, int pvc) {
        if (dd[town]) return;
        rep (i, 1, n) {
            if (i == town || i == pvc) continue;
            if (dd[i])
                continue;
            cur.push({town, i, Dist(town, i)});
        }
    }

    void solution() {
        compress();
        priority_queue<Data, vector<Data>, cmp> setA;

        rep (k, 1, K) {
            pair<int,int> town;
            ll mnVal = INF;
            ST1.init(numY), ST2.init(numY);
            rep (i, 1, n) {
                int pos = lower_bound(ALL(cY), a[i].y) - cY.begin() + 1;
                if (dd[i] == 1) {
                    ST1.update (pos, mp(INF + 1, i));
                    ST2.update (pos, mp(INF + 1, i));
                    continue;
                }
                int B1 = ST1.get (1, pos).se, B2 = ST2.get (pos, numY).se;
                if (B1 != -1 && Dist (i, B1) < mnVal) {
                    mnVal = Dist(i, B1);
                    town = {i, B1};
                }
                if (B2 != -1 && Dist (i, B2) < mnVal) {
                    mnVal = Dist (i, B2);
                    town = {i, B2};
                }
                ST1.update (pos, mp(-a[i].x - a[i].y, i));
                ST2.update (pos, mp(-a[i].x + a[i].y, i));
            }
            if (!setA.empty()) {
                pair<int,int> cur = {setA.top().A, setA.top().B};
                if (Dist (cur.fs, cur.se) < mnVal) {
                    mnVal = Dist (cur.fs, cur.se);
                    town = cur;
                    setA.pop();
                }
            }
            addtoset(setA, town.fs, town.se);
            addtoset(setA, town.se, town.fs);
            dd[town.fs] = dd[town.se] = 1;
            cout << mnVal<<"\n";
        }
    }
}

namespace sub5 {
    int m;
    Coor b[N];
    vector<ll> Ans;

    bool check (ll X, int trace) {
        set<pair<ll, int>> S;
        int ptr = 1;
        int res = 0;
        rep (i, 1, n) {
            while (ptr < i && b[ptr].x < b[i].x - X) {
                S.erase(S.find(mp(b[ptr].y, ptr)));
                ++ptr;
            }
            for (auto it = S.lower_bound(mp(b[i].y - X, 0)); it != S.end(); ++it) {
                if (it->fs > b[i].y + X)
                    break;
                if(trace == 0) ++res;
                else if (SZ(Ans) < K) Ans.push_back(max(abs(b[i].x - b[it->se].x), abs(b[i].y - b[it->se].y)));
                if (res == K) return 1;
            }
            S.insert(mp(b[i].y, i));
        }
        return 0;
    }
    void BS (ll L, ll R) {
        while (L < R) {
            ll mid = L + R >> 1;
            if (check(mid, 0)) R = mid;
            else L = mid + 1;
        }
        check(L - 1, 1);
        while (SZ(Ans) < K) Ans.push_back(L);
        sort (ALL(Ans));
        iter (&id, Ans) cout << id <<"\n";
    }
    void solution() {
//        cout << check(3, 4) <<"\n";
        rep (i, 1, n) {
            b[i].x = {a[i].x - a[i].y};
            b[i].y = {a[i].x + a[i].y};
        }
        sort (b + 1, b + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
        BS(1, 4e9);

    }
}

namespace sub2 {
    bool check () {
        rep (i, 1, n) if (a[i].y != 0) return 0;
        return 1;
    }
    void solution() {

        struct Data {
            int pos, lf, val;
        };
        struct cmp {
            bool operator () (Data A, Data B) { return A.val > B.val; }
        };
        priority_queue<Data, vector<Data>, cmp> pq;
        rep (i, 2, n) {
            pq.push({i, i - 1, a[i].x - a[i - 1].x});
        }
        vector<int> Ans;
        while(!pq.empty()) {
            int u = pq.top().pos, prv = pq.top().lf;
            pq.pop();
            Ans.push_back(a[u].x - a[prv].x);
            if (SZ(Ans) >= K) break;
            if (prv > 1) {
                pq.push({u, prv - 1, a[u].x - a[prv - 1].x});
            }
        }
        iter (&id, Ans) cout << id <<"\n";
    }
}

void solution () {
    cin >> n >> K;
    rep (i, 1, n) {
        cin >> a[i].x >> a[i].y;
    }
    sort (a + 1, a + 1 + n, [] (Coor A, Coor B) { return A.x < B.x; });
//    rep (i, 1, n) cout <<a[i].x<< ","<<a[i].y<<" ";
//    cout<<"\n";
    if (sub2 :: check())
        sub2 :: solution();
    else
        if (K <= 10)
        sub4 :: solution();
    else
        sub5 :: solution();

}

#define file(name) freopen(name".inp", "r", stdin); \
//freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/

Compilation message (stderr)

road_construction.cpp: In member function 'void sub4::Segment_Tree::update(int, int, int, int, std::pair<long long int, int>)':
road_construction.cpp:56:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |             int mid = l + r >> 1;
      |                       ~~^~~
road_construction.cpp: In member function 'std::pair<long long int, int> sub4::Segment_Tree::get(int, int, int, int, int)':
road_construction.cpp:64:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int mid = l + r >> 1;
      |                       ~~^~~
road_construction.cpp: In function 'void sub5::BS(long long int, long long int)':
road_construction.cpp:174:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |             ll mid = L + R >> 1;
      |                      ~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35