oj.uz

Submission #867412

# Submission time Handle Problem Language Result Execution time Memory
867412 2023-10-28T11:00:55 Z azberjibiou Road Construction (JOI21_road_construction) C++17
100 / 100
 8894 ms 120136 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(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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 54860 KB Output is correct
2 Correct 69 ms 54716 KB Output is correct
3 Correct 47 ms 54584 KB Output is correct
4 Correct 48 ms 54720 KB Output is correct
5 Correct 55 ms 53612 KB Output is correct
6 Correct 21 ms 50180 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7189 ms 118780 KB Output is correct
2 Correct 7197 ms 118768 KB Output is correct
3 Correct 49 ms 54436 KB Output is correct
4 Correct 7069 ms 119908 KB Output is correct
5 Correct 6853 ms 117976 KB Output is correct
6 Correct 6815 ms 118972 KB Output is correct
7 Correct 6987 ms 118716 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7699 ms 118964 KB Output is correct
2 Correct 7718 ms 120136 KB Output is correct
3 Correct 9 ms 49752 KB Output is correct
4 Correct 6793 ms 119932 KB Output is correct
5 Correct 4331 ms 118548 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7699 ms 118964 KB Output is correct
2 Correct 7718 ms 120136 KB Output is correct
3 Correct 9 ms 49752 KB Output is correct
4 Correct 6793 ms 119932 KB Output is correct
5 Correct 4331 ms 118548 KB Output is correct
6 Correct 7720 ms 118240 KB Output is correct
7 Correct 7687 ms 118512 KB Output is correct
8 Correct 9 ms 49752 KB Output is correct
9 Correct 9 ms 49756 KB Output is correct
10 Correct 7426 ms 119680 KB Output is correct
11 Correct 6747 ms 118556 KB Output is correct
12 Correct 4321 ms 118468 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 54860 KB Output is correct
2 Correct 69 ms 54716 KB Output is correct
3 Correct 47 ms 54584 KB Output is correct
4 Correct 48 ms 54720 KB Output is correct
5 Correct 55 ms 53612 KB Output is correct
6 Correct 21 ms 50180 KB Output is correct
7 Correct 3143 ms 89408 KB Output is correct
8 Correct 3124 ms 89344 KB Output is correct
9 Correct 48 ms 54684 KB Output is correct
10 Correct 2853 ms 88016 KB Output is correct
11 Correct 2780 ms 88736 KB Output is correct
12 Correct 1630 ms 88536 KB Output is correct
13 Correct 1787 ms 87380 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 54860 KB Output is correct
2 Correct 69 ms 54716 KB Output is correct
3 Correct 47 ms 54584 KB Output is correct
4 Correct 48 ms 54720 KB Output is correct
5 Correct 55 ms 53612 KB Output is correct
6 Correct 21 ms 50180 KB Output is correct
7 Correct 7189 ms 118780 KB Output is correct
8 Correct 7197 ms 118768 KB Output is correct
9 Correct 49 ms 54436 KB Output is correct
10 Correct 7069 ms 119908 KB Output is correct
11 Correct 6853 ms 117976 KB Output is correct
12 Correct 6815 ms 118972 KB Output is correct
13 Correct 6987 ms 118716 KB Output is correct
14 Correct 7699 ms 118964 KB Output is correct
15 Correct 7718 ms 120136 KB Output is correct
16 Correct 9 ms 49752 KB Output is correct
17 Correct 6793 ms 119932 KB Output is correct
18 Correct 4331 ms 118548 KB Output is correct
19 Correct 7720 ms 118240 KB Output is correct
20 Correct 7687 ms 118512 KB Output is correct
21 Correct 9 ms 49752 KB Output is correct
22 Correct 9 ms 49756 KB Output is correct
23 Correct 7426 ms 119680 KB Output is correct
24 Correct 6747 ms 118556 KB Output is correct
25 Correct 4321 ms 118468 KB Output is correct
26 Correct 3143 ms 89408 KB Output is correct
27 Correct 3124 ms 89344 KB Output is correct
28 Correct 48 ms 54684 KB Output is correct
29 Correct 2853 ms 88016 KB Output is correct
30 Correct 2780 ms 88736 KB Output is correct
31 Correct 1630 ms 88536 KB Output is correct
32 Correct 1787 ms 87380 KB Output is correct
33 Correct 8536 ms 119248 KB Output is correct
34 Correct 8894 ms 119520 KB Output is correct
35 Correct 7699 ms 118540 KB Output is correct
36 Correct 3979 ms 118988 KB Output is correct
37 Correct 4120 ms 118656 KB Output is correct
38 Correct 4436 ms 119868 KB Output is correct