oj.uz

Submission #867418

# Submission time Handle Problem Language Result Execution time Memory
867418 2023-10-28T11:07:49 Z azberjibiou Road Construction (JOI21_road_construction) C++17
100 / 100
 9269 ms 751148 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{
    queue <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].push(val);
            else    seg[idx].pop();
            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){
        int sz=seg[idx].size();
        while(sz--){
            v.push_back(seg[idx].front());
            seg[idx].push(seg[idx].front());
            seg[idx].pop();
        }
        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), [](qry a, qry b){
        if(a.y!=b.y)   return a.y<b.y;
        if(a.typ!=b.typ)   return a.typ<b.typ;
        return A[a.ix].se<A[b.ix].se;
    });
    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:136: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]
  136 |         if(uly+1!=cry.size())   ct.emplace_back(2, uly+1, dlx, ulx, i);
      |            ~~~~~^~~~~~~~~~~~
road_construction.cpp:157:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     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 449 ms 680620 KB Output is correct
2 Correct 438 ms 680596 KB Output is correct
3 Correct 402 ms 680500 KB Output is correct
4 Correct 359 ms 680496 KB Output is correct
5 Correct 368 ms 679488 KB Output is correct
6 Correct 374 ms 676044 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7475 ms 746360 KB Output is correct
2 Correct 7598 ms 746836 KB Output is correct
3 Correct 398 ms 680248 KB Output is correct
4 Correct 7426 ms 747192 KB Output is correct
5 Correct 7281 ms 746508 KB Output is correct
6 Correct 7238 ms 747140 KB Output is correct
7 Correct 7343 ms 746848 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8193 ms 747624 KB Output is correct
2 Correct 8416 ms 747324 KB Output is correct
3 Correct 376 ms 675480 KB Output is correct
4 Correct 7405 ms 745512 KB Output is correct
5 Correct 4882 ms 750812 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8193 ms 747624 KB Output is correct
2 Correct 8416 ms 747324 KB Output is correct
3 Correct 376 ms 675480 KB Output is correct
4 Correct 7405 ms 745512 KB Output is correct
5 Correct 4882 ms 750812 KB Output is correct
6 Correct 8352 ms 750168 KB Output is correct
7 Correct 8371 ms 749704 KB Output is correct
8 Correct 350 ms 675412 KB Output is correct
9 Correct 347 ms 675408 KB Output is correct
10 Correct 8349 ms 751084 KB Output is correct
11 Correct 7173 ms 747832 KB Output is correct
12 Correct 4726 ms 750148 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 680620 KB Output is correct
2 Correct 438 ms 680596 KB Output is correct
3 Correct 402 ms 680500 KB Output is correct
4 Correct 359 ms 680496 KB Output is correct
5 Correct 368 ms 679488 KB Output is correct
6 Correct 374 ms 676044 KB Output is correct
7 Correct 3525 ms 716612 KB Output is correct
8 Correct 3526 ms 715548 KB Output is correct
9 Correct 375 ms 680500 KB Output is correct
10 Correct 3210 ms 716424 KB Output is correct
11 Correct 3197 ms 714552 KB Output is correct
12 Correct 1998 ms 714568 KB Output is correct
13 Correct 2194 ms 712632 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 680620 KB Output is correct
2 Correct 438 ms 680596 KB Output is correct
3 Correct 402 ms 680500 KB Output is correct
4 Correct 359 ms 680496 KB Output is correct
5 Correct 368 ms 679488 KB Output is correct
6 Correct 374 ms 676044 KB Output is correct
7 Correct 7475 ms 746360 KB Output is correct
8 Correct 7598 ms 746836 KB Output is correct
9 Correct 398 ms 680248 KB Output is correct
10 Correct 7426 ms 747192 KB Output is correct
11 Correct 7281 ms 746508 KB Output is correct
12 Correct 7238 ms 747140 KB Output is correct
13 Correct 7343 ms 746848 KB Output is correct
14 Correct 8193 ms 747624 KB Output is correct
15 Correct 8416 ms 747324 KB Output is correct
16 Correct 376 ms 675480 KB Output is correct
17 Correct 7405 ms 745512 KB Output is correct
18 Correct 4882 ms 750812 KB Output is correct
19 Correct 8352 ms 750168 KB Output is correct
20 Correct 8371 ms 749704 KB Output is correct
21 Correct 350 ms 675412 KB Output is correct
22 Correct 347 ms 675408 KB Output is correct
23 Correct 8349 ms 751084 KB Output is correct
24 Correct 7173 ms 747832 KB Output is correct
25 Correct 4726 ms 750148 KB Output is correct
26 Correct 3525 ms 716612 KB Output is correct
27 Correct 3526 ms 715548 KB Output is correct
28 Correct 375 ms 680500 KB Output is correct
29 Correct 3210 ms 716424 KB Output is correct
30 Correct 3197 ms 714552 KB Output is correct
31 Correct 1998 ms 714568 KB Output is correct
32 Correct 2194 ms 712632 KB Output is correct
33 Correct 9269 ms 750108 KB Output is correct
34 Correct 8899 ms 751016 KB Output is correct
35 Correct 8055 ms 749768 KB Output is correct
36 Correct 4404 ms 751120 KB Output is correct
37 Correct 4547 ms 750284 KB Output is correct
38 Correct 4879 ms 751148 KB Output is correct