oj.uz

Submission #446972

# Submission time Handle Problem Language Result Execution time Memory
446972 2021-07-24T06:59:15 Z jk410 Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 22612 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
multiset<int> S[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 (register 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 (register 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;
}

Compilation message

road_construction.cpp: In function 'void init()':
road_construction.cpp:24:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   24 |     for (register int i=1; i<(Tree_size<<1); i++)
      |                       ^
road_construction.cpp: In function 'll f(ll, bool)':
road_construction.cpp:44:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |     for (register int i=1,s=1; i<=N; i++){
      |                       ^
road_construction.cpp:44:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |     for (register int i=1,s=1; i<=N; i++){
      |                           ^
road_construction.cpp:62:31: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   62 |             for (register int t=l; t<=r; t++){
      |                               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 18752 KB Output is correct
2 Correct 72 ms 18812 KB Output is correct
3 Correct 64 ms 18880 KB Output is correct
4 Correct 64 ms 18872 KB Output is correct
5 Correct 66 ms 17600 KB Output is correct
6 Correct 15 ms 14140 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 22468 KB Output is correct
2 Correct 1784 ms 22576 KB Output is correct
3 Correct 62 ms 18660 KB Output is correct
4 Correct 1696 ms 22436 KB Output is correct
5 Correct 1588 ms 22572 KB Output is correct
6 Correct 1593 ms 22612 KB Output is correct
7 Correct 1631 ms 22344 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3847 ms 19356 KB Output is correct
2 Correct 3952 ms 19436 KB Output is correct
3 Execution timed out 10079 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 3847 ms 19356 KB Output is correct
2 Correct 3952 ms 19436 KB Output is correct
3 Execution timed out 10079 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 70 ms 18752 KB Output is correct
2 Correct 72 ms 18812 KB Output is correct
3 Correct 64 ms 18880 KB Output is correct
4 Correct 64 ms 18872 KB Output is correct
5 Correct 66 ms 17600 KB Output is correct
6 Correct 15 ms 14140 KB Output is correct
7 Correct 1829 ms 20448 KB Output is correct
8 Correct 1813 ms 20444 KB Output is correct
9 Correct 64 ms 18880 KB Output is correct
10 Correct 1427 ms 19768 KB Output is correct
11 Correct 1278 ms 19548 KB Output is correct
12 Correct 443 ms 18496 KB Output is correct
13 Correct 445 ms 19016 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 18752 KB Output is correct
2 Correct 72 ms 18812 KB Output is correct
3 Correct 64 ms 18880 KB Output is correct
4 Correct 64 ms 18872 KB Output is correct
5 Correct 66 ms 17600 KB Output is correct
6 Correct 15 ms 14140 KB Output is correct
7 Correct 1774 ms 22468 KB Output is correct
8 Correct 1784 ms 22576 KB Output is correct
9 Correct 62 ms 18660 KB Output is correct
10 Correct 1696 ms 22436 KB Output is correct
11 Correct 1588 ms 22572 KB Output is correct
12 Correct 1593 ms 22612 KB Output is correct
13 Correct 1631 ms 22344 KB Output is correct
14 Correct 3847 ms 19356 KB Output is correct
15 Correct 3952 ms 19436 KB Output is correct
16 Execution timed out 10079 ms 14028 KB Time limit exceeded
17 Halted 0 ms 0 KB -