oj.uz

Submission #921746

# Submission time Handle Problem Language Result Execution time Memory
921746 2024-02-04T09:47:18 Z guagua0407 Road Construction (JOI21_road_construction) C++17
100 / 100
 9570 ms 63904 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();
        }
        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;
                //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])));
            }
            S.insert({vec[v.f].s,v.f});
            dq.push_back(v.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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6080 KB Output is correct
2 Correct 45 ms 6108 KB Output is correct
3 Correct 40 ms 6100 KB Output is correct
4 Correct 37 ms 6244 KB Output is correct
5 Correct 39 ms 5052 KB Output is correct
6 Correct 7 ms 1512 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7133 ms 58300 KB Output is correct
2 Correct 7167 ms 58296 KB Output is correct
3 Correct 36 ms 6104 KB Output is correct
4 Correct 7950 ms 61148 KB Output is correct
5 Correct 7685 ms 61168 KB Output is correct
6 Correct 7684 ms 61392 KB Output is correct
7 Correct 7194 ms 60592 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7627 ms 58492 KB Output is correct
2 Correct 7579 ms 57980 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7635 ms 60144 KB Output is correct
5 Correct 1983 ms 15836 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7627 ms 58492 KB Output is correct
2 Correct 7579 ms 57980 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 7635 ms 60144 KB Output is correct
5 Correct 1983 ms 15836 KB Output is correct
6 Correct 8836 ms 57260 KB Output is correct
7 Correct 8727 ms 57048 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 8541 ms 54112 KB Output is correct
11 Correct 9297 ms 60152 KB Output is correct
12 Correct 2013 ms 15608 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6080 KB Output is correct
2 Correct 45 ms 6108 KB Output is correct
3 Correct 40 ms 6100 KB Output is correct
4 Correct 37 ms 6244 KB Output is correct
5 Correct 39 ms 5052 KB Output is correct
6 Correct 7 ms 1512 KB Output is correct
7 Correct 2621 ms 29804 KB Output is correct
8 Correct 2577 ms 29292 KB Output is correct
9 Correct 49 ms 6248 KB Output is correct
10 Correct 2388 ms 26368 KB Output is correct
11 Correct 2208 ms 25764 KB Output is correct
12 Correct 737 ms 12552 KB Output is correct
13 Correct 755 ms 10712 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6080 KB Output is correct
2 Correct 45 ms 6108 KB Output is correct
3 Correct 40 ms 6100 KB Output is correct
4 Correct 37 ms 6244 KB Output is correct
5 Correct 39 ms 5052 KB Output is correct
6 Correct 7 ms 1512 KB Output is correct
7 Correct 7133 ms 58300 KB Output is correct
8 Correct 7167 ms 58296 KB Output is correct
9 Correct 36 ms 6104 KB Output is correct
10 Correct 7950 ms 61148 KB Output is correct
11 Correct 7685 ms 61168 KB Output is correct
12 Correct 7684 ms 61392 KB Output is correct
13 Correct 7194 ms 60592 KB Output is correct
14 Correct 7627 ms 58492 KB Output is correct
15 Correct 7579 ms 57980 KB Output is correct
16 Correct 1 ms 1368 KB Output is correct
17 Correct 7635 ms 60144 KB Output is correct
18 Correct 1983 ms 15836 KB Output is correct
19 Correct 8836 ms 57260 KB Output is correct
20 Correct 8727 ms 57048 KB Output is correct
21 Correct 1 ms 1368 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 8541 ms 54112 KB Output is correct
24 Correct 9297 ms 60152 KB Output is correct
25 Correct 2013 ms 15608 KB Output is correct
26 Correct 2621 ms 29804 KB Output is correct
27 Correct 2577 ms 29292 KB Output is correct
28 Correct 49 ms 6248 KB Output is correct
29 Correct 2388 ms 26368 KB Output is correct
30 Correct 2208 ms 25764 KB Output is correct
31 Correct 737 ms 12552 KB Output is correct
32 Correct 755 ms 10712 KB Output is correct
33 Correct 9570 ms 63892 KB Output is correct
34 Correct 9250 ms 63904 KB Output is correct
35 Correct 7895 ms 52092 KB Output is correct
36 Correct 1821 ms 20064 KB Output is correct
37 Correct 1856 ms 20188 KB Output is correct
38 Correct 2134 ms 21884 KB Output is correct