oj.uz

Submission #446971

# Submission time Handle Problem Language Result Execution time Memory
446971 2021-07-24T06:52:20 Z jk410 Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 25388 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;
set<int> S[250001];
void init(){
    for (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 (Point[i].y-Point[s].y>m){
            update(Point[s].idx,-1);
            if (flag)
                S[Point[s].idx].erase(S[Point[s].idx].find(Point[s].y));
            s++;
        }
        int l=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x-m)-Cor_X.begin(),r;
        auto it=lower_bound(Cor_X.begin(),Cor_X.end(),Point[i].x+m);
        if (it==Cor_X.end())
            r=Size-1;
        else if (*it==Point[i].x+m)
            r=it-Cor_X.begin();
        else
            r=it-Cor_X.begin()-1;
        if (l<=r)
            ret+=query(l,r);
        if (flag){
            for (int t=l; t<=r; t++){
                for (int y:S[t]){
                    Dist.push_back(max(abs((ll)Point[i].x-Cor_X[t]),(ll)Point[i].y-y));
                    Cnt--;
                }
            }
            S[Point[i].idx].insert(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)>>1;
        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 18900 KB Output is correct
2 Correct 68 ms 18816 KB Output is correct
3 Correct 63 ms 18880 KB Output is correct
4 Correct 62 ms 18944 KB Output is correct
5 Correct 60 ms 17596 KB Output is correct
6 Correct 13 ms 14156 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1735 ms 25244 KB Output is correct
2 Correct 1626 ms 25248 KB Output is correct
3 Correct 66 ms 18756 KB Output is correct
4 Correct 1582 ms 25144 KB Output is correct
5 Correct 1575 ms 25268 KB Output is correct
6 Correct 1540 ms 25388 KB Output is correct
7 Correct 1492 ms 25240 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3963 ms 24236 KB Output is correct
2 Correct 3837 ms 24260 KB Output is correct
3 Execution timed out 10010 ms 14028 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3963 ms 24236 KB Output is correct
2 Correct 3837 ms 24260 KB Output is correct
3 Execution timed out 10010 ms 14028 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 18900 KB Output is correct
2 Correct 68 ms 18816 KB Output is correct
3 Correct 63 ms 18880 KB Output is correct
4 Correct 62 ms 18944 KB Output is correct
5 Correct 60 ms 17596 KB Output is correct
6 Correct 13 ms 14156 KB Output is correct
7 Correct 1904 ms 22140 KB Output is correct
8 Correct 1938 ms 22276 KB Output is correct
9 Correct 63 ms 18940 KB Output is correct
10 Correct 1444 ms 21424 KB Output is correct
11 Correct 1268 ms 21336 KB Output is correct
12 Correct 401 ms 20272 KB Output is correct
13 Correct 395 ms 20752 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 18900 KB Output is correct
2 Correct 68 ms 18816 KB Output is correct
3 Correct 63 ms 18880 KB Output is correct
4 Correct 62 ms 18944 KB Output is correct
5 Correct 60 ms 17596 KB Output is correct
6 Correct 13 ms 14156 KB Output is correct
7 Correct 1735 ms 25244 KB Output is correct
8 Correct 1626 ms 25248 KB Output is correct
9 Correct 66 ms 18756 KB Output is correct
10 Correct 1582 ms 25144 KB Output is correct
11 Correct 1575 ms 25268 KB Output is correct
12 Correct 1540 ms 25388 KB Output is correct
13 Correct 1492 ms 25240 KB Output is correct
14 Correct 3963 ms 24236 KB Output is correct
15 Correct 3837 ms 24260 KB Output is correct
16 Execution timed out 10010 ms 14028 KB Time limit exceeded
17 Halted 0 ms 0 KB -