oj.uz

Submission #867395

# Submission time Handle Problem Language Result Execution time Memory
867395 2023-10-28T10:19:41 Z azberjibiou Road Construction (JOI21_road_construction) C++17
100 / 100
 8512 ms 125084 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=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(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

# Verdict Execution time Memory Grader output
1 Correct 66 ms 54864 KB Output is correct
2 Correct 70 ms 54904 KB Output is correct
3 Correct 49 ms 54708 KB Output is correct
4 Correct 49 ms 54648 KB Output is correct
5 Correct 56 ms 53704 KB Output is correct
6 Correct 21 ms 50168 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7419 ms 121052 KB Output is correct
2 Correct 7277 ms 122672 KB Output is correct
3 Correct 53 ms 54440 KB Output is correct
4 Correct 7089 ms 123068 KB Output is correct
5 Correct 6964 ms 122260 KB Output is correct
6 Correct 7022 ms 122368 KB Output is correct
7 Correct 6982 ms 121924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7755 ms 121336 KB Output is correct
2 Correct 7769 ms 123668 KB Output is correct
3 Correct 10 ms 49756 KB Output is correct
4 Correct 6982 ms 121296 KB Output is correct
5 Correct 4469 ms 123656 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7755 ms 121336 KB Output is correct
2 Correct 7769 ms 123668 KB Output is correct
3 Correct 10 ms 49756 KB Output is correct
4 Correct 6982 ms 121296 KB Output is correct
5 Correct 4469 ms 123656 KB Output is correct
6 Correct 7777 ms 123636 KB Output is correct
7 Correct 7795 ms 123588 KB Output is correct
8 Correct 9 ms 49752 KB Output is correct
9 Correct 9 ms 49756 KB Output is correct
10 Correct 7469 ms 125084 KB Output is correct
11 Correct 6950 ms 121700 KB Output is correct
12 Correct 4426 ms 123536 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 54864 KB Output is correct
2 Correct 70 ms 54904 KB Output is correct
3 Correct 49 ms 54708 KB Output is correct
4 Correct 49 ms 54648 KB Output is correct
5 Correct 56 ms 53704 KB Output is correct
6 Correct 21 ms 50168 KB Output is correct
7 Correct 3278 ms 90204 KB Output is correct
8 Correct 3252 ms 90224 KB Output is correct
9 Correct 50 ms 54648 KB Output is correct
10 Correct 2943 ms 87440 KB Output is correct
11 Correct 2813 ms 88292 KB Output is correct
12 Correct 1708 ms 88812 KB Output is correct
13 Correct 1765 ms 86144 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 54864 KB Output is correct
2 Correct 70 ms 54904 KB Output is correct
3 Correct 49 ms 54708 KB Output is correct
4 Correct 49 ms 54648 KB Output is correct
5 Correct 56 ms 53704 KB Output is correct
6 Correct 21 ms 50168 KB Output is correct
7 Correct 7419 ms 121052 KB Output is correct
8 Correct 7277 ms 122672 KB Output is correct
9 Correct 53 ms 54440 KB Output is correct
10 Correct 7089 ms 123068 KB Output is correct
11 Correct 6964 ms 122260 KB Output is correct
12 Correct 7022 ms 122368 KB Output is correct
13 Correct 6982 ms 121924 KB Output is correct
14 Correct 7755 ms 121336 KB Output is correct
15 Correct 7769 ms 123668 KB Output is correct
16 Correct 10 ms 49756 KB Output is correct
17 Correct 6982 ms 121296 KB Output is correct
18 Correct 4469 ms 123656 KB Output is correct
19 Correct 7777 ms 123636 KB Output is correct
20 Correct 7795 ms 123588 KB Output is correct
21 Correct 9 ms 49752 KB Output is correct
22 Correct 9 ms 49756 KB Output is correct
23 Correct 7469 ms 125084 KB Output is correct
24 Correct 6950 ms 121700 KB Output is correct
25 Correct 4426 ms 123536 KB Output is correct
26 Correct 3278 ms 90204 KB Output is correct
27 Correct 3252 ms 90224 KB Output is correct
28 Correct 50 ms 54648 KB Output is correct
29 Correct 2943 ms 87440 KB Output is correct
30 Correct 2813 ms 88292 KB Output is correct
31 Correct 1708 ms 88812 KB Output is correct
32 Correct 1765 ms 86144 KB Output is correct
33 Correct 8469 ms 123952 KB Output is correct
34 Correct 8512 ms 123524 KB Output is correct
35 Correct 7742 ms 124200 KB Output is correct
36 Correct 4159 ms 124324 KB Output is correct
37 Correct 4294 ms 123828 KB Output is correct
38 Correct 4455 ms 125056 KB Output is correct