oj.uz

Submission #921741

# Submission time Handle Problem Language Result Execution time Memory
921741 2024-02-04T09:45:05 Z guagua0407 Road Construction (JOI21_road_construction) C++17
33 / 100
 9293 ms 64328 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=250005;
const ll inf=2e9+5;
int n,k;
vector<pair<int,int>> vec;
vector<int> xs,ys;
vector<vector<int>> sir,sir2;
int bit[mxn];

void update(int pos,int val){
    pos++;
    for(;pos<mxn;pos+=(pos&-pos)){
        bit[pos]+=val;
    }
}

int query(int pos){
    pos++;
    int ans=0;
    for(;pos>0;pos-=(pos&-pos)){
        ans+=bit[pos];
    }
    return ans;
}

bool ok(ll d){
    vector<vector<pair<int,int>>> st(xs.size());
    vector<vector<pair<int,pair<int,int>>>> en(xs.size());
    for(int i=0;i<n;i++){
        int l=lower_bound(all(xs),max(-inf,(ll)xs[vec[i].f]-d))-xs.begin();
        int r=upper_bound(all(xs),min(inf,(ll)xs[vec[i].f]+d))-xs.begin()-1;
        int l2=lower_bound(all(ys),max(-inf,(ll)ys[vec[i].s]-d))-ys.begin();
        int r2=upper_bound(all(ys),min(inf,(ll)ys[vec[i].s]+d))-ys.begin()-1;
        if(l>0){
            st[l-1].push_back({l2,r2});
        }
        en[vec[i].f].push_back({vec[i].s,{l2,r2}});
    }
    memset(bit,0,sizeof(bit));
    ll ans=0;
    for(int i=0;i<(int)xs.size();i++){
        for(auto v:en[i]){
            ans+=(query(v.s.s)-query(v.s.f-1));
            update(v.f,1);
        }
        for(auto v:st[i]){
            ans-=(query(v.s)-query(v.f-1));
        }
        //if(ans>=k) return true;
    }
    //cout<<d<<' '<<ans<<'\n';
    return ans>=k;
}

signed main() {_
    cin>>n>>k;
    vec.resize(n);
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        int xx=y+x;
        int yy=y-x;
        vec[i]={xx,yy};
        xs.push_back(xx);
        ys.push_back(yy);
    }
    sort(all(xs));
    sort(all(ys));
    xs.resize(unique(all(xs))-xs.begin());
    ys.resize(unique(all(ys))-ys.begin());
    sir.resize(xs.size());
    sir2.resize(xs.size());
    for(int i=0;i<n;i++){
        //cout<<vec[i].f<<' '<<vec[i].s<<'\n';
        vec[i].f=lower_bound(all(xs),vec[i].f)-xs.begin();
        vec[i].s=lower_bound(all(ys),vec[i].s)-ys.begin();
        sir[vec[i].f].push_back(vec[i].s);
        sir2[vec[i].f].push_back(i);
    }
    ll l=0,r=(ll)4e9;
    while(l<r){
        ll mid=(l+r)/2;
        if(ok(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    //cout<<l<<'\n';
    //return 0;
    ll d=l-1;
    vector<vector<pair<int,pair<int,int>>>> en(xs.size());
    for(int i=0;i<n;i++){
        int l2=lower_bound(all(ys),max(-inf,(ll)ys[vec[i].s]-d))-ys.begin();
        int r2=upper_bound(all(ys),min(inf,(ll)ys[vec[i].s]+d))-ys.begin()-1;
        en[vec[i].f].push_back({i,{l2,r2}});
    }
    set<pair<int,int>> S;
    deque<int> dq;
    vector<ll> ans;
    for(int i=0;i<(int)xs.size();i++){
        //cout<<xs[i]<<'\n';
        while(!dq.empty() and xs[vec[dq[0]].f]<max(-inf,(ll)xs[i]-d)){
            //cout<<"xxx "<<dq[0]<<' ';
            S.erase({vec[dq[0]].s,dq[0]});
            dq.pop_front();
        }
        //cout<<'\n';
        for(auto v:sir2[i]){
            S.insert({vec[v].s,v});
            dq.push_back(v);
        }
        for(auto v:en[i]){
            auto r=S.upper_bound({v.s.s,inf});
            for(auto it=S.lower_bound({v.s.f,-inf});it!=r;it++){
                int x=(*it).s;
                if(x==v.f) continue;
                //cout<<x<<' '<<v.f<<'\n';
                ans.push_back(max(abs((ll)ys[vec[x].s]-(ll)ys[vec[v.f].s]),abs((ll)xs[vec[x].f]-(ll)xs[vec[v.f].f])));
            }
        }
        //cout<<'\n';
    }
    sort(all(ans));
    while((int)ans.size()<k){
        ans.push_back(l);
    }
    for(auto v:ans){
        cout<<v<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message

road_construction.cpp: In function 'bool ok(long long int)':
road_construction.cpp:48:13: warning: unused variable 'r' [-Wunused-variable]
   48 |         int r=upper_bound(all(xs),min(inf,(ll)xs[vec[i].f]+d))-xs.begin()-1;
      |             ^
road_construction.cpp: In function 'void setIO(std::string)':
road_construction.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6336 KB Output is correct
2 Correct 44 ms 6316 KB Output is correct
3 Correct 43 ms 6356 KB Output is correct
4 Correct 40 ms 6360 KB Output is correct
5 Incorrect 39 ms 5132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8023 ms 58296 KB Output is correct
2 Correct 7998 ms 61316 KB Output is correct
3 Correct 34 ms 6104 KB Output is correct
4 Correct 9022 ms 64192 KB Output is correct
5 Correct 9293 ms 64104 KB Output is correct
6 Correct 7994 ms 64328 KB Output is correct
7 Correct 7127 ms 64004 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8063 ms 58412 KB Output is correct
2 Correct 8722 ms 57772 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7653 ms 60372 KB Output is correct
5 Correct 1968 ms 15800 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8063 ms 58412 KB Output is correct
2 Correct 8722 ms 57772 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7653 ms 60372 KB Output is correct
5 Correct 1968 ms 15800 KB Output is correct
6 Correct 9002 ms 57256 KB Output is correct
7 Correct 7838 ms 62332 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 7767 ms 59256 KB Output is correct
11 Correct 8697 ms 63080 KB Output is correct
12 Correct 2012 ms 20980 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6336 KB Output is correct
2 Correct 44 ms 6316 KB Output is correct
3 Correct 43 ms 6356 KB Output is correct
4 Correct 40 ms 6360 KB Output is correct
5 Incorrect 39 ms 5132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6336 KB Output is correct
2 Correct 44 ms 6316 KB Output is correct
3 Correct 43 ms 6356 KB Output is correct
4 Correct 40 ms 6360 KB Output is correct
5 Incorrect 39 ms 5132 KB Output isn't correct
6 Halted 0 ms 0 KB -