oj.uz

Submission #446988

# Submission time Handle Problem Language Result Execution time Memory
446988 2021-07-24T07:48:51 Z jk410 Road Construction (JOI21_road_construction) C++17
100 / 100
 5515 ms 184944 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    struct point{
        int x,y,idx;
        bool operator<(const point &t)const{
            if (y!=t.y)
                return y<t.y;
            return x<t.x;
        }
    };
    const int Tree_size=1<<18;
    const ll INF=4e9;
    int N,Cnt,Size;
    ll K,Ans;
    int Tree[Tree_size<<1],L[250001],R[250001];
    point Point[250001];
    vector<ll> Cor_X,Dist;
    deque<int> Y[250001];
    void init(){
        for (register int i=1; i<(Tree_size<<1); i++)
            Tree[i]=0;
    }
    void update(int idx,int v){
        for (idx+=Tree_size; idx; idx>>=1)
            Tree[idx]+=v;
    }
    int query(int l,int r){
        int ret=0;
        for (l+=Tree_size,r+=Tree_size; l<=r; l>>=1,r>>=1){
            if (l&1)
                ret+=Tree[l++];
            if (!(r&1))
                ret+=Tree[r--];
        }
        return ret;
    }
    ll f(ll m,bool flag){
        ll ret=0;
        init();
        for (int i=1,s=1; i<=N; i++){
            while ((ll)Point[i].y-Point[s].y>m){
                update(Point[s].idx,-1);
                if (flag)
                    Y[Point[s].idx].pop_front();
                s++;
            }
            int l=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x-m)-Cor_X.begin(),r=upper_bound(Cor_X.begin(),Cor_X.end(),Point[i].x+m)-Cor_X.begin()-1;
            if (l<=r)
                ret+=query(l,r);
            if (flag){
                for (int t=l; t<=r; t++){
                    for (int y:Y[t]){
                        Dist.push_back(max(abs((ll)Point[i].x-Cor_X[t]),(ll)Point[i].y-y));
                        Cnt--;
                    }
                }
                Y[Point[i].idx].push_back(Point[i].y);
            }
            update(Point[i].idx,1);
        }
        return ret;
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cin>>N>>K;
        for (int i=1; i<=N; i++){
            int x,y;
            cin>>x>>y;
            Point[i]={x+y,x-y};
            Cor_X.push_back(Point[i].x);
        }
        sort(Point+1,Point+N+1);
        sort(Cor_X.begin(),Cor_X.end());
        Cor_X.erase(unique(Cor_X.begin(),Cor_X.end()),Cor_X.end());
        Size=Cor_X.size();
        for (int i=1; i<=N; i++)
            Point[i].idx=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x)-Cor_X.begin();
        ll l=0,r=INF;
        while (l<=r){
            ll m=(l+r)/2;
            if (f(m,false)>=K){
                Ans=m;
                r=m-1;
            }
            else
                l=m+1;
        }
        Cnt=K;
        f(Ans-1,true);
        sort(Dist.begin(),Dist.end());
        for (ll i:Dist)
            cout<<i<<"\n";
        while (Cnt--)
            cout<<Ans<<"\n";
        return 0;
    }

Compilation message

road_construction.cpp: In function 'void init()':
road_construction.cpp:21:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   21 |         for (register int i=1; i<(Tree_size<<1); i++)
      |                           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 175360 KB Output is correct
2 Correct 172 ms 175408 KB Output is correct
3 Correct 175 ms 175464 KB Output is correct
4 Correct 166 ms 175480 KB Output is correct
5 Correct 171 ms 174192 KB Output is correct
6 Correct 128 ms 170732 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1740 ms 181572 KB Output is correct
2 Correct 1740 ms 181552 KB Output is correct
3 Correct 171 ms 175280 KB Output is correct
4 Correct 1708 ms 181316 KB Output is correct
5 Correct 1614 ms 181572 KB Output is correct
6 Correct 1631 ms 181504 KB Output is correct
7 Correct 1621 ms 181352 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3892 ms 178500 KB Output is correct
2 Correct 3883 ms 178608 KB Output is correct
3 Correct 116 ms 170564 KB Output is correct
4 Correct 1547 ms 178632 KB Output is correct
5 Correct 1077 ms 180912 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3892 ms 178500 KB Output is correct
2 Correct 3883 ms 178608 KB Output is correct
3 Correct 116 ms 170564 KB Output is correct
4 Correct 1547 ms 178632 KB Output is correct
5 Correct 1077 ms 180912 KB Output is correct
6 Correct 3846 ms 180672 KB Output is correct
7 Correct 3871 ms 180888 KB Output is correct
8 Correct 119 ms 170712 KB Output is correct
9 Correct 116 ms 170536 KB Output is correct
10 Correct 3808 ms 180896 KB Output is correct
11 Correct 1606 ms 178512 KB Output is correct
12 Correct 1064 ms 181040 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 175360 KB Output is correct
2 Correct 172 ms 175408 KB Output is correct
3 Correct 175 ms 175464 KB Output is correct
4 Correct 166 ms 175480 KB Output is correct
5 Correct 171 ms 174192 KB Output is correct
6 Correct 128 ms 170732 KB Output is correct
7 Correct 2016 ms 178684 KB Output is correct
8 Correct 2023 ms 178684 KB Output is correct
9 Correct 179 ms 175416 KB Output is correct
10 Correct 1491 ms 178084 KB Output is correct
11 Correct 1362 ms 177900 KB Output is correct
12 Correct 500 ms 176736 KB Output is correct
13 Correct 494 ms 177452 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 175360 KB Output is correct
2 Correct 172 ms 175408 KB Output is correct
3 Correct 175 ms 175464 KB Output is correct
4 Correct 166 ms 175480 KB Output is correct
5 Correct 171 ms 174192 KB Output is correct
6 Correct 128 ms 170732 KB Output is correct
7 Correct 1740 ms 181572 KB Output is correct
8 Correct 1740 ms 181552 KB Output is correct
9 Correct 171 ms 175280 KB Output is correct
10 Correct 1708 ms 181316 KB Output is correct
11 Correct 1614 ms 181572 KB Output is correct
12 Correct 1631 ms 181504 KB Output is correct
13 Correct 1621 ms 181352 KB Output is correct
14 Correct 3892 ms 178500 KB Output is correct
15 Correct 3883 ms 178608 KB Output is correct
16 Correct 116 ms 170564 KB Output is correct
17 Correct 1547 ms 178632 KB Output is correct
18 Correct 1077 ms 180912 KB Output is correct
19 Correct 3846 ms 180672 KB Output is correct
20 Correct 3871 ms 180888 KB Output is correct
21 Correct 119 ms 170712 KB Output is correct
22 Correct 116 ms 170536 KB Output is correct
23 Correct 3808 ms 180896 KB Output is correct
24 Correct 1606 ms 178512 KB Output is correct
25 Correct 1064 ms 181040 KB Output is correct
26 Correct 2016 ms 178684 KB Output is correct
27 Correct 2023 ms 178684 KB Output is correct
28 Correct 179 ms 175416 KB Output is correct
29 Correct 1491 ms 178084 KB Output is correct
30 Correct 1362 ms 177900 KB Output is correct
31 Correct 500 ms 176736 KB Output is correct
32 Correct 494 ms 177452 KB Output is correct
33 Correct 5515 ms 184944 KB Output is correct
34 Correct 5508 ms 184668 KB Output is correct
35 Correct 3910 ms 183972 KB Output is correct
36 Correct 1063 ms 182876 KB Output is correct
37 Correct 1072 ms 182928 KB Output is correct
38 Correct 1170 ms 184108 KB Output is correct