oj.uz

Submission #541672

# Submission time Handle Problem Language Result Execution time Memory
541672 2022-03-24T06:44:58 Z Fysty Road Construction (JOI21_road_construction) C++17
100 / 100
 5087 ms 20400 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const ll INF=3e18;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end());uni(c)
const ll C=4e9;
const int N=250005;

ll n,k;
vector<pll> p;
vector<ll> v;

struct BIT
{
    ll sz,a[N];
    void init()
    {
        rep1(i,sz) a[i]=0;
    }
    void upd(ll x,ll val)
    {
        for(;x<=sz;x+=x&-x) a[x]+=val;
    }
    ll qry(ll x)
    {
        ll ret=0;
        for(;x;x-=x&-x) ret+=a[x];
        return ret;
    }
} bit;

ll calc(ll d)
{
    ll ret=0;
    ll l=0;
    bit.init();
    rep(i,n)
    {
        while(l<i&&p[i].F-p[l].F>d)
        {
            ll id=lower_bound(v.begin(),v.end(),p[l].S)-v.begin()+1;
            bit.upd(id,-1);
            l++;
        }
        ll ql=lower_bound(v.begin(),v.end(),p[i].S-d)-v.begin()+1;
        ll qr=upper_bound(v.begin(),v.end(),p[i].S+d)-v.begin();
        ret+=bit.qry(qr)-bit.qry(ql-1);
        ll id=lower_bound(v.begin(),v.end(),p[i].S)-v.begin()+1;
        bit.upd(id,1);
    }
    return ret;
}

void getans(ll d,ll k)
{
    if(d==0)
    {
        rep(i,k) cout<<"0\n";
        return;
    }
    vector<ll> ans;
    multiset<pll> s;
    ll l=0;
    rep(i,n)
    {
        while(l<i&&p[i].F-p[l].F>d-1)
        {
            s.erase(s.find({p[l].S,p[l].F}));
            l++;
        }
        auto qr=s.upper_bound({p[i].S+d-1,INF});
        for(auto it=s.lower_bound({p[i].S-d+1,-INF});it!=qr;it++)
        {
            pll q=*it;
            swap(q.F,q.S);
            ans.pb(max(abs(q.F-p[i].F),abs(q.S-p[i].S)));
        }
        s.insert({p[i].S,p[i].F});
    }
    sort(ans.begin(),ans.end());
    for(ll u:ans) cout<<u<<"\n";
    ll r=k-ans.size();
    rep(_,r) cout<<d<<"\n";
}
signed main()
{
    MottoHayaku

    cin>>n>>k;
    rep(i,n)
    {
        ll X,Y;
        cin>>X>>Y;
        p.pb({X-Y,X+Y});
        v.pb(X+Y);
    }
    unisort(v);
    sort(p.begin(),p.end());
    ll l=1,r=C;
    bit.sz=v.size();
    while(l<r)
    {
        ll mid=l+r>>1;
        ll tmp=calc(mid);
        if(tmp<k) l=mid+1;
        else r=mid;
    }
    getans(l,k);
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:116:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         ll mid=l+r>>1;
      |                ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5060 KB Output is correct
2 Correct 46 ms 5044 KB Output is correct
3 Correct 43 ms 5048 KB Output is correct
4 Correct 45 ms 5120 KB Output is correct
5 Correct 42 ms 3908 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2012 ms 17320 KB Output is correct
2 Correct 1935 ms 17324 KB Output is correct
3 Correct 42 ms 4928 KB Output is correct
4 Correct 1912 ms 17324 KB Output is correct
5 Correct 1837 ms 17352 KB Output is correct
6 Correct 1835 ms 17456 KB Output is correct
7 Correct 1846 ms 16800 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4574 ms 15276 KB Output is correct
2 Correct 4589 ms 15272 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1836 ms 13108 KB Output is correct
5 Correct 1426 ms 13584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4574 ms 15276 KB Output is correct
2 Correct 4589 ms 15272 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1836 ms 13108 KB Output is correct
5 Correct 1426 ms 13584 KB Output is correct
6 Correct 4720 ms 15276 KB Output is correct
7 Correct 4691 ms 15276 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4533 ms 15124 KB Output is correct
11 Correct 1813 ms 13132 KB Output is correct
12 Correct 1410 ms 13584 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5060 KB Output is correct
2 Correct 46 ms 5044 KB Output is correct
3 Correct 43 ms 5048 KB Output is correct
4 Correct 45 ms 5120 KB Output is correct
5 Correct 42 ms 3908 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1878 ms 12016 KB Output is correct
8 Correct 1815 ms 12020 KB Output is correct
9 Correct 43 ms 5164 KB Output is correct
10 Correct 1654 ms 11148 KB Output is correct
11 Correct 1583 ms 10940 KB Output is correct
12 Correct 457 ms 7612 KB Output is correct
13 Correct 553 ms 9816 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5060 KB Output is correct
2 Correct 46 ms 5044 KB Output is correct
3 Correct 43 ms 5048 KB Output is correct
4 Correct 45 ms 5120 KB Output is correct
5 Correct 42 ms 3908 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 2012 ms 17320 KB Output is correct
8 Correct 1935 ms 17324 KB Output is correct
9 Correct 42 ms 4928 KB Output is correct
10 Correct 1912 ms 17324 KB Output is correct
11 Correct 1837 ms 17352 KB Output is correct
12 Correct 1835 ms 17456 KB Output is correct
13 Correct 1846 ms 16800 KB Output is correct
14 Correct 4574 ms 15276 KB Output is correct
15 Correct 4589 ms 15272 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1836 ms 13108 KB Output is correct
18 Correct 1426 ms 13584 KB Output is correct
19 Correct 4720 ms 15276 KB Output is correct
20 Correct 4691 ms 15276 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4533 ms 15124 KB Output is correct
24 Correct 1813 ms 13132 KB Output is correct
25 Correct 1410 ms 13584 KB Output is correct
26 Correct 1878 ms 12016 KB Output is correct
27 Correct 1815 ms 12020 KB Output is correct
28 Correct 43 ms 5164 KB Output is correct
29 Correct 1654 ms 11148 KB Output is correct
30 Correct 1583 ms 10940 KB Output is correct
31 Correct 457 ms 7612 KB Output is correct
32 Correct 553 ms 9816 KB Output is correct
33 Correct 5053 ms 20400 KB Output is correct
34 Correct 5087 ms 20148 KB Output is correct
35 Correct 4502 ms 18984 KB Output is correct
36 Correct 1173 ms 15300 KB Output is correct
37 Correct 1210 ms 15256 KB Output is correct
38 Correct 1578 ms 17136 KB Output is correct