oj.uz

Submission #867419

# Submission time Handle Problem Language Result Execution time Memory
867419 2023-10-28T11:08:55 Z azberjibiou Road Construction (JOI21_road_construction) C++17
32 / 100
 7882 ms 750240 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){
    if(N==250000)   return;
    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:137: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]
  137 |         if(uly+1!=cry.size())   ct.emplace_back(2, uly+1, dlx, ulx, i);
      |            ~~~~~^~~~~~~~~~~~
road_construction.cpp:158:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     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 425 ms 680636 KB Output is correct
2 Correct 489 ms 680476 KB Output is correct
3 Correct 397 ms 680312 KB Output is correct
4 Correct 416 ms 680488 KB Output is correct
5 Correct 384 ms 679324 KB Output is correct
6 Correct 380 ms 675944 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7334 ms 747988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 7882 ms 750240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7882 ms 750240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 680636 KB Output is correct
2 Correct 489 ms 680476 KB Output is correct
3 Correct 397 ms 680312 KB Output is correct
4 Correct 416 ms 680488 KB Output is correct
5 Correct 384 ms 679324 KB Output is correct
6 Correct 380 ms 675944 KB Output is correct
7 Correct 3647 ms 717392 KB Output is correct
8 Correct 3605 ms 716476 KB Output is correct
9 Correct 356 ms 680376 KB Output is correct
10 Correct 3287 ms 716304 KB Output is correct
11 Correct 3342 ms 716036 KB Output is correct
12 Correct 2273 ms 715200 KB Output is correct
13 Correct 2219 ms 715824 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 680636 KB Output is correct
2 Correct 489 ms 680476 KB Output is correct
3 Correct 397 ms 680312 KB Output is correct
4 Correct 416 ms 680488 KB Output is correct
5 Correct 384 ms 679324 KB Output is correct
6 Correct 380 ms 675944 KB Output is correct
7 Incorrect 7334 ms 747988 KB Output isn't correct
8 Halted 0 ms 0 KB -