oj.uz

Submission #945872

# Submission time Handle Problem Language Result Execution time Memory
945872 2024-03-14T08:18:22 Z beepbeepsheep Road Construction (JOI21_road_construction) C++17
100 / 100
 5754 ms 171480 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif // DEBUG

const ll maxn=2e5+5e4+5;
const ll inf=1e15;
const ll mod=1e9+7;

ll n;
ll x[maxn],y[maxn];
ii ranges[maxn];
vector<ll> pos;
vector<ii> updates;
ll fen[maxn];
void upd(ll x, ll v){
    while (x<maxn){
        fen[x]+=v;
        x+=(x&-x);
    }
}
ll query(ll x){
    ll ans=0;
    while (x){
        ans+=fen[x];
        x-=(x&-x);
    }
    return ans;
}
ll query(ll x, ll y){
    return query(y)-query(x-1);
}
ll check(ll len){
    vector<tuple<ll,ll,ll>> queries;
    for (int i=1;i<=n;i++){
        queries.emplace_back(y[i]-len-1,i,-1);
        //exclusive
        queries.emplace_back(y[i]+len,i,1);
        //inclusive
        ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
                        -pos.begin();
        ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
                        -pos.begin()-1;
    }
    sort(queries.begin(),queries.end());
    ll ans=0,ptr=0;
    memset(fen,0,sizeof(fen));
    for (auto [a,b,c]:queries){
        while (ptr!=updates.size() &&
               updates[ptr].first<=a){
            upd(updates[ptr].second,1);
            ptr++;
        }
        ans+=c*(query(ranges[b].first,ranges[b].second));
    }
    return (ans-n)/2;
}
struct node{
    ll s,e,m;
    vector<ii> v;
    node *l,*r;
    node(ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ii p){
        if (s==e){
            v.emplace_back(p);
            return;
        }
        if (x>m) r->upd(x,p);
        else l->upd(x,p);
    }
    void build(){
        if (s!=e){
            l->build(),r->build();
            for (auto u:l->v) v.emplace_back(u);
            for (auto u:r->v) v.emplace_back(u);
        }
        sort(v.begin(),v.end()); //remember to put y first
    }
    vector<ll> query(ll x, ll y, ll v1, ll v2, ii p){
        if (x<=s && e<=y){
            ll x1,y1;
            tie(y1,x1)=p;
            ll lb=lower_bound(v.begin(),v.end(),
                              make_pair(v1,-inf))-v.begin();
            ll ub=upper_bound(v.begin(),v.end(),
                              make_pair(v2,inf))-v.begin();
            vector<ll> out;
            for (int i=lb;i<ub;i++){
                ll x2,y2;
                tie(y2,x2)=v[i];
                if (x1==x2 && y1==y2) continue;
                out.emplace_back(max(abs(x1-x2),abs(y1-y2)));
            }
            return out;
        }
        if (x>m) return r->query(x,y,v1,v2,p);
        if (y<=m) return l->query(x,y,v1,v2,p);
        vector<ll> out1=l->query(x,y,v1,v2,p);
        vector<ll> out2=r->query(x,y,v1,v2,p);
        for (auto u:out1) out2.emplace_back(u);
        return out2;
    }
}*root;
ll flat[maxn];
vector<ll> out;
void solve(ll len){
    for (int i=1;i<=n;i++){
        ranges[i].first=lower_bound(pos.begin(),pos.end(),x[i]-len)
                        -pos.begin();
        ranges[i].second=upper_bound(pos.begin(),pos.end(),x[i]+len)
                        -pos.begin()-1;
    }
    root=new node(1,n);
    for (int i=1;i<=n;i++){
        root->upd(flat[i],make_pair(y[i],x[i]));
    }
    root->build();
    for (int i=1;i<=n;i++){
        ll l,r;
        tie(l,r)=ranges[i];
        vector<ll> roads=root->query(l,r,y[i]-len,
                                     y[i]+len,make_pair(y[i],x[i]));
        //left x, right x, bottom y, top y, central point
        for (auto u:roads) out.emplace_back(u);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll a,b,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a>>b;
        x[i]=a+b,y[i]=a-b;
        pos.emplace_back(x[i]);
    }
    pos.emplace_back(-inf);
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    for (int i=1;i<=n;i++){
        flat[i]=lower_bound(pos.begin(),pos.end(),x[i])
                -pos.begin();
        updates.emplace_back(y[i],flat[i]);
    }
    sort(updates.begin(),updates.end());
    ll l=1,r=4'000'000'005,m;
    while (l!=r-1){
        m=(l+r)>>1;
        if (check(m)>=k) r=m; //we need to reach r
        else l=m;
    }
    //find everything <=l
    solve(l);
    sort(out.begin(),out.end());
    while (out.size()<2*k) out.emplace_back(r);
    for (int i=0;i<out.size();i+=2) cout<<out[i]<<endl;
    return 0;
}

Compilation message

road_construction.cpp: In function 'long long int check(long long int)':
road_construction.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while (ptr!=updates.size() &&
      |                ~~~^~~~~~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:165:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  165 |     while (out.size()<2*k) out.emplace_back(r);
      |            ~~~~~~~~~~^~~~
road_construction.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (int i=0;i<out.size();i+=2) cout<<out[i]<<endl;
      |                  ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15564 KB Output is correct
2 Correct 79 ms 15688 KB Output is correct
3 Correct 61 ms 15608 KB Output is correct
4 Correct 63 ms 15728 KB Output is correct
5 Correct 60 ms 14552 KB Output is correct
6 Correct 12 ms 9052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4589 ms 153424 KB Output is correct
2 Correct 4520 ms 155872 KB Output is correct
3 Correct 57 ms 15368 KB Output is correct
4 Correct 4456 ms 155660 KB Output is correct
5 Correct 4439 ms 153984 KB Output is correct
6 Correct 4521 ms 153920 KB Output is correct
7 Correct 4423 ms 153720 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5091 ms 145504 KB Output is correct
2 Correct 5051 ms 150580 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4221 ms 149012 KB Output is correct
5 Correct 3432 ms 148008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5091 ms 145504 KB Output is correct
2 Correct 5051 ms 150580 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 4221 ms 149012 KB Output is correct
5 Correct 3432 ms 148008 KB Output is correct
6 Correct 4982 ms 151036 KB Output is correct
7 Correct 4977 ms 150604 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 4834 ms 167292 KB Output is correct
11 Correct 4239 ms 148720 KB Output is correct
12 Correct 3514 ms 147936 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15564 KB Output is correct
2 Correct 79 ms 15688 KB Output is correct
3 Correct 61 ms 15608 KB Output is correct
4 Correct 63 ms 15728 KB Output is correct
5 Correct 60 ms 14552 KB Output is correct
6 Correct 12 ms 9052 KB Output is correct
7 Correct 2064 ms 75728 KB Output is correct
8 Correct 2032 ms 77856 KB Output is correct
9 Correct 57 ms 15540 KB Output is correct
10 Correct 1791 ms 75044 KB Output is correct
11 Correct 1706 ms 76148 KB Output is correct
12 Correct 1308 ms 72152 KB Output is correct
13 Correct 1331 ms 71248 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 15564 KB Output is correct
2 Correct 79 ms 15688 KB Output is correct
3 Correct 61 ms 15608 KB Output is correct
4 Correct 63 ms 15728 KB Output is correct
5 Correct 60 ms 14552 KB Output is correct
6 Correct 12 ms 9052 KB Output is correct
7 Correct 4589 ms 153424 KB Output is correct
8 Correct 4520 ms 155872 KB Output is correct
9 Correct 57 ms 15368 KB Output is correct
10 Correct 4456 ms 155660 KB Output is correct
11 Correct 4439 ms 153984 KB Output is correct
12 Correct 4521 ms 153920 KB Output is correct
13 Correct 4423 ms 153720 KB Output is correct
14 Correct 5091 ms 145504 KB Output is correct
15 Correct 5051 ms 150580 KB Output is correct
16 Correct 3 ms 8540 KB Output is correct
17 Correct 4221 ms 149012 KB Output is correct
18 Correct 3432 ms 148008 KB Output is correct
19 Correct 4982 ms 151036 KB Output is correct
20 Correct 4977 ms 150604 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 4834 ms 167292 KB Output is correct
24 Correct 4239 ms 148720 KB Output is correct
25 Correct 3514 ms 147936 KB Output is correct
26 Correct 2064 ms 75728 KB Output is correct
27 Correct 2032 ms 77856 KB Output is correct
28 Correct 57 ms 15540 KB Output is correct
29 Correct 1791 ms 75044 KB Output is correct
30 Correct 1706 ms 76148 KB Output is correct
31 Correct 1308 ms 72152 KB Output is correct
32 Correct 1331 ms 71248 KB Output is correct
33 Correct 5754 ms 158808 KB Output is correct
34 Correct 5622 ms 158764 KB Output is correct
35 Correct 4945 ms 171480 KB Output is correct
36 Correct 3341 ms 151860 KB Output is correct
37 Correct 3473 ms 150916 KB Output is correct
38 Correct 3529 ms 156056 KB Output is correct