oj.uz

Submission #921721

# Submission time Handle Problem Language Result Execution time Memory
921721 2024-02-04T09:29:46 Z guagua0407 Road Construction (JOI21_road_construction) C++17
33 / 100
 9731 ms 64200 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()),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({l2,r2});
    }
    memset(bit,0,sizeof(bit));
    ll ans=0;
    for(int i=0;i<(int)xs.size();i++){
        for(auto v:sir[i]){
            update(v,1);
        }
        for(auto v:st[i]){
            ans-=(query(v.s)-query(v.f-1));
        }
        for(auto v:en[i]){
            ans+=(query(v.s)-query(v.f-1));
        }
        if(ans-n>=k) return true;
    }
    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';
    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:47:13: warning: unused variable 'r' [-Wunused-variable]
   47 |         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 52 ms 6332 KB Output is correct
2 Correct 44 ms 6332 KB Output is correct
3 Correct 44 ms 6112 KB Output is correct
4 Correct 40 ms 6364 KB Output is correct
5 Incorrect 43 ms 5008 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 7854 ms 58288 KB Output is correct
2 Correct 7588 ms 61320 KB Output is correct
3 Correct 35 ms 6100 KB Output is correct
4 Correct 7757 ms 63932 KB Output is correct
5 Correct 7998 ms 64108 KB Output is correct
6 Correct 7928 ms 64200 KB Output is correct
7 Correct 7136 ms 63800 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9731 ms 58500 KB Output is correct
2 Correct 9012 ms 57772 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7810 ms 60144 KB Output is correct
5 Correct 1931 ms 14016 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9731 ms 58500 KB Output is correct
2 Correct 9012 ms 57772 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7810 ms 60144 KB Output is correct
5 Correct 1931 ms 14016 KB Output is correct
6 Correct 9176 ms 57260 KB Output is correct
7 Correct 8571 ms 62344 KB Output is correct
8 Correct 2 ms 1368 KB Output is correct
9 Correct 1 ms 1368 KB Output is correct
10 Correct 8415 ms 59424 KB Output is correct
11 Correct 7866 ms 63100 KB Output is correct
12 Correct 1959 ms 19376 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6332 KB Output is correct
2 Correct 44 ms 6332 KB Output is correct
3 Correct 44 ms 6112 KB Output is correct
4 Correct 40 ms 6364 KB Output is correct
5 Incorrect 43 ms 5008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6332 KB Output is correct
2 Correct 44 ms 6332 KB Output is correct
3 Correct 44 ms 6112 KB Output is correct
4 Correct 40 ms 6364 KB Output is correct
5 Incorrect 43 ms 5008 KB Output isn't correct
6 Halted 0 ms 0 KB -