Submission #867412

#	Time	Username	Problem	Language	Result	Execution time	Memory
867412		azberjibiou	Road Construction (JOI21_road_construction)	C++17	100 / 100	8894 ms	120136 KiB

road_construction

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=250030;
const int mxM=500004;
const int MOD=998244353;
const ll INF=8e18;
typedef struct qry{
    int typ;
    ll y, x1, x2;
    int ix;
    qry() : typ(), y(), x1(), x2(), ix() {}
    qry(int typ, ll y, ll x1, ll x2) : typ(typ), y(y), x1(x1), x2(x2), ix(){}
    qry(int typ, ll y, ll x1, ll x2, int ix) : typ(typ), y(y), x1(x1), x2(x2), ix(ix){}
    bool operator<(qry a){
        if(a.y!=y)  return y<a.y;
        return typ<a.typ;
    }
}qry;
typedef struct BIT{ ///zero indexed
    int fen[mxN], n;
    void set_n(int m){n=m;}
    void init(){for(int i=0;i<=n;i++) fen[i]=0;}
    void upd(int i){i++; for(;i<=n;i+=(i&(-i))) fen[i]++;}
    int sum(int i){int res=0; for(;i>0;i-=(i&(-i))) res+=fen[i]; return res;}
    int solv(int s, int e){s++; e++; return sum(e)-sum(s-1);}
}BIT;
typedef struct segtree{
    set <int> seg[4*mxN];
    void upd(int idx, int s1, int e1, int s2, int e2, int val, int typ){
        if(s2>e1 || s1>e2)  return;
        if(s2<=s1 && e1<=e2){
            if(typ==1)  seg[idx].insert(val);
            else    seg[idx].erase(val);
            return;
        }
        int mid=(s1+e1)/2;
        upd(2*idx, s1, mid, s2, e2, val, typ);
        upd(2*idx+1, mid+1, e1, s2, e2, val, typ);
    }
    void solv(int idx, int s1, int e1, int pos, vector <int> &v){
        for(int ele : seg[idx]) v.push_back(ele);
        if(s1==e1)  return;
        int mid=(s1+e1)/2;
        if(pos<=mid)    solv(2*idx, s1, mid, pos, v);
        else    solv(2*idx+1, mid+1, e1, pos, v);
    }
}segtree;
int N, K;
pll A[mxN];
vector <ll> crx, cry;
BIT T1;
segtree T2;
void input(){
    cin >> N >> K;
    for(int i=1;i<=N;i++)   cin >> A[i].fi >> A[i].se, A[i]=pll(A[i].fi+A[i].se, A[i].fi-A[i].se);
}
void compress(vector <ll> &v){
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
void make_coor(){
    for(int i=1;i<=N;i++){
        auto [x, y]=A[i];
        crx.push_back(x);
        cry.push_back(y);
    }
    compress(crx);
    compress(cry);
    for(int i=1;i<=N;i++){
        auto &[x, y]=A[i];
        x=lower_bound(all(crx), x)-crx.begin();
        y=lower_bound(all(cry), y)-cry.begin();
    }
}
ll solv1(ll d){
    ll res=0;
    vector <qry> ct;    ///1: add point, 2: minus 구간, 3: plus 구간
    T1.set_n(crx.size());
    T1.init();
    for(int i=1;i<=N;i++){
        auto [x, y]=A[i];
        ll ulx, dlx, uly, dly;
        ulx=upper_bound(all(crx), crx[x]+d)-crx.begin()-1;
        uly=upper_bound(all(cry), cry[y]+d)-cry.begin()-1;
        dlx=lower_bound(all(crx), crx[x]-d)-crx.begin();
        dly=lower_bound(all(cry), cry[y]-d)-cry.begin();
        if(dly!=0)  ct.emplace_back(2, dly-1, dlx, ulx);
        ct.emplace_back(3, uly, dlx, ulx);
        ct.emplace_back(1, y, x, x);
    }
    sort(all(ct));
    for(auto [typ, y, x1, x2, _] : ct)
    {
        if(typ==1){
            T1.upd(x1);
        }
        else{
            int sgn=(typ==2 ? -1 : 1);
            int val=T1.solv(x1, x2);
            res+=sgn*val;
        }
    }
    return (res-N)/2;
}
ll dist(int a, int b)
{
    pll na=pll(crx[A[a].fi], cry[A[a].se]);
    pll nb=pll(crx[A[b].fi], cry[A[b].se]);
    return max(abs(na.fi-nb.fi), abs(na.se-nb.se));
}
void solv2(ll d){
    vector <ll> dis;
    vector <qry> ct;    ///1: add 구간, 2: delete 구간, 3: add point
    for(int i=1;i<=N;i++){
        auto [x, y]=A[i];
        ll ulx, dlx, uly, dly;
        ulx=upper_bound(all(crx), crx[x]+d)-crx.begin()-1;
        uly=upper_bound(all(cry), cry[y]+d)-cry.begin()-1;
        dlx=lower_bound(all(crx), crx[x]-d)-crx.begin();
        dly=lower_bound(all(cry), cry[y]-d)-cry.begin();
        ct.emplace_back(1, dly, dlx, ulx, i);
        if(uly+1!=cry.size())   ct.emplace_back(2, uly+1, dlx, ulx, i);
        ct.emplace_back(3, y, x, x, i);
    }
    sort(all(ct));
    for(auto [typ, y, x1, x2, ix] : ct)
    {
        if(typ<=2){
            T2.upd(1, 0, crx.size()-1, x1, x2, ix, typ);
        }
        else{
            vector <int> nv;
            T2.solv(1, 0, crx.size()-1, x1, nv);
            for(int ele : nv)   if(ele>ix)  dis.push_back(dist(ele, ix));
        }
    }
    sort(all(dis));
    for(ll ele : dis)   cout << ele << '\n';
    for(int i=0;i<K-dis.size();i++) cout << d+1 << '\n';
}
int main()
{
    gibon
    input();
    make_coor();
    ll s=0, e=4'000'000'001;
    while(s!=e)
    {
        ll mid=(s+e)/2;
        if(solv1(mid)>=K)  e=mid;
        else    s=mid+1;
    }
    solv2(s-1);
}

Compilation message (stderr)

road_construction.cpp: In function 'void solv2(ll)':
road_construction.cpp:131:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(uly+1!=cry.size())   ct.emplace_back(2, uly+1, dlx, ulx, i);
      |            ~~~~~^~~~~~~~~~~~
road_construction.cpp:148:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i=0;i<K-dis.size();i++) cout << d+1 << '\n';
      |                 ~^~~~~~~~~~~~~

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