oj.uz

답안 #867394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867394 2023-10-28T10:19:31 Z azberjibiou Road Construction (JOI21_road_construction) C++17
32 / 100
 3153 ms 60572 KB 
#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=100030;
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(int i=0;i<K;i++)    cout << dis[i] << '\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);
}

Compilation message

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);
      |            ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 26012 KB Output is correct
2 Correct 57 ms 26048 KB Output is correct
3 Correct 51 ms 25856 KB Output is correct
4 Correct 44 ms 25896 KB Output is correct
5 Correct 51 ms 25276 KB Output is correct
6 Correct 16 ms 21472 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 22364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 23120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 23120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 26012 KB Output is correct
2 Correct 57 ms 26048 KB Output is correct
3 Correct 51 ms 25856 KB Output is correct
4 Correct 44 ms 25896 KB Output is correct
5 Correct 51 ms 25276 KB Output is correct
6 Correct 16 ms 21472 KB Output is correct
7 Correct 3153 ms 59100 KB Output is correct
8 Correct 3131 ms 60572 KB Output is correct
9 Correct 44 ms 26016 KB Output is correct
10 Correct 2939 ms 59460 KB Output is correct
11 Correct 2895 ms 59268 KB Output is correct
12 Correct 1753 ms 59620 KB Output is correct
13 Correct 1851 ms 58536 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 26012 KB Output is correct
2 Correct 57 ms 26048 KB Output is correct
3 Correct 51 ms 25856 KB Output is correct
4 Correct 44 ms 25896 KB Output is correct
5 Correct 51 ms 25276 KB Output is correct
6 Correct 16 ms 21472 KB Output is correct
7 Incorrect 16 ms 22364 KB Output isn't correct
8 Halted 0 ms 0 KB -