제출 #1255912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255912		yeongminb	Road Construction (JOI21_road_construction)	C++20	0 / 100	10101 ms	372976 KiB

road_construction

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
struct SegmentTree{
public:
    ll n; vector<multiset<ll>> tree;
    SegmentTree(ll N){
        n = N;
        tree.resize(4 * n);
    }
    void update(ll idx, ll val) {update(1, 0, n-1, idx, val);}
    multiset<ll> query(ll l, ll r, ll T){
        multiset<ll> rtv;
        if(l > r) return rtv;
        query(1, 0, n-1, l, r, T, rtv);
        return rtv;
    }
private:
    void update(ll node, ll st, ll en, ll idx, ll val){
        if(st == en) tree[node].insert(val);
        else {
            ll mid = (st + en)/2;
            if(idx <= mid) update(2*node, st, mid, idx, val);
            else update(2*node+1, mid+1, en, idx, val);
            tree[node].insert(val);
        }
    }
    void query(ll node, ll st, ll en, ll l, ll r, ll T, multiset<ll> &ms){
        if(st > r || en < l) return;
        if(l <= st && en <= r){
            for(auto &c : tree[node]){
                if(ms.size() == T && *(prev(ms.end())) <= c) break; 
                ms.insert(c);
                if(ms.size() == T+1) ms.erase(prev(ms.end()));
            }
        } else {
            ll mid = (st + en)/2;
            query(2*node, st, mid, l, r, T, ms);
            query(2*node+1, mid+1, en, l, r, T, ms);
        }
    }
};

ll getIdx(vector<ll> &cmp, ll x){
    return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
}

int main(){
    fastio;
    ll N, K; cin >> N >> K;
    multiset<ll> ans;
    vector<pii> coord(N);
    vector<ll> xcmp, ycmp;
    for(auto &[x,y] : coord) {
        cin >> x >> y;
        xcmp.push_back(x);
        ycmp.push_back(y);
    }

    sort(xcmp.begin(), xcmp.end());
    sort(ycmp.begin(), ycmp.end());
    xcmp.erase(unique(xcmp.begin(), xcmp.end()), xcmp.end());
    ycmp.erase(unique(ycmp.begin(), ycmp.end()), ycmp.end());

    SegmentTree seg1(ycmp.size());
    sort(coord.begin(), coord.end());
    for(auto [x,y] : coord){
        multiset<ll> ms = seg1.query(0, getIdx(ycmp, y)-1, 250);
        for(auto c : ms) ans.insert(x+y+c);
        seg1.update(getIdx(ycmp, y), -x-y);
    }

    SegmentTree seg2(ycmp.size());
    for(auto [x,y] : coord){
        multiset<ll> ms = seg2.query(getIdx(ycmp,y), ycmp.size(), 250);
        for(auto c : ms) ans.insert(x-y+c);
        seg2.update(getIdx(ycmp, y), -x+y);
    }

    for(auto c : ans){
        if(K-- == 0) break;
        cout << c << "\n";
    }
}

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