oj.uz

Submission #446982

# Submission time Handle Problem Language Result Execution time Memory
446982 2021-07-24T07:20:06 Z jk410 Road Construction (JOI21_road_construction) C++17
38 / 100
 4062 ms 345792 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;
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 (register int i=1,s=1; i<=N; i++){
        while (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;
        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: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)>>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 178 ms 175276 KB Output is correct
2 Correct 176 ms 175248 KB Output is correct
3 Correct 174 ms 175408 KB Output is correct
4 Correct 170 ms 175464 KB Output is correct
5 Correct 185 ms 174272 KB Output is correct
6 Correct 130 ms 170720 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1816 ms 178756 KB Output is correct
2 Correct 1812 ms 178992 KB Output is correct
3 Correct 184 ms 175304 KB Output is correct
4 Correct 1713 ms 178632 KB Output is correct
5 Correct 1631 ms 178888 KB Output is correct
6 Correct 1658 ms 178912 KB Output is correct
7 Correct 1689 ms 178728 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4062 ms 175788 KB Output is correct
2 Correct 3934 ms 175688 KB Output is correct
3 Runtime error 275 ms 345792 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4062 ms 175788 KB Output is correct
2 Correct 3934 ms 175688 KB Output is correct
3 Runtime error 275 ms 345792 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 175276 KB Output is correct
2 Correct 176 ms 175248 KB Output is correct
3 Correct 174 ms 175408 KB Output is correct
4 Correct 170 ms 175464 KB Output is correct
5 Correct 185 ms 174272 KB Output is correct
6 Correct 130 ms 170720 KB Output is correct
7 Correct 2083 ms 176904 KB Output is correct
8 Correct 2090 ms 177020 KB Output is correct
9 Correct 179 ms 175464 KB Output is correct
10 Correct 1558 ms 176168 KB Output is correct
11 Correct 1418 ms 176080 KB Output is correct
12 Correct 571 ms 174984 KB Output is correct
13 Correct 579 ms 175540 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 175276 KB Output is correct
2 Correct 176 ms 175248 KB Output is correct
3 Correct 174 ms 175408 KB Output is correct
4 Correct 170 ms 175464 KB Output is correct
5 Correct 185 ms 174272 KB Output is correct
6 Correct 130 ms 170720 KB Output is correct
7 Correct 1816 ms 178756 KB Output is correct
8 Correct 1812 ms 178992 KB Output is correct
9 Correct 184 ms 175304 KB Output is correct
10 Correct 1713 ms 178632 KB Output is correct
11 Correct 1631 ms 178888 KB Output is correct
12 Correct 1658 ms 178912 KB Output is correct
13 Correct 1689 ms 178728 KB Output is correct
14 Correct 4062 ms 175788 KB Output is correct
15 Correct 3934 ms 175688 KB Output is correct
16 Runtime error 275 ms 345792 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -