oj.uz

Submission #921750

# Submission time Handle Problem Language Result Execution time Memory
921750 2024-02-04T09:48:35 Z guagua0407 Road Construction (JOI21_road_construction) C++17
100 / 100
 8508 ms 61172 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 55 ms 6080 KB Output is correct
3 Correct 39 ms 6100 KB Output is correct
4 Correct 39 ms 6360 KB Output is correct
5 Correct 40 ms 5052 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7743 ms 58300 KB Output is correct
2 Correct 7711 ms 58288 KB Output is correct
3 Correct 35 ms 6104 KB Output is correct
4 Correct 7741 ms 61116 KB Output is correct
5 Correct 8022 ms 61172 KB Output is correct
6 Correct 8101 ms 61172 KB Output is correct
7 Correct 6986 ms 60584 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8508 ms 58536 KB Output is correct
2 Correct 8125 ms 57780 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 8287 ms 60340 KB Output is correct
5 Correct 1955 ms 15440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8508 ms 58536 KB Output is correct
2 Correct 8125 ms 57780 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 8287 ms 60340 KB Output is correct
5 Correct 1955 ms 15440 KB Output is correct
6 Correct 7423 ms 57264 KB Output is correct
7 Correct 7156 ms 57260 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 7325 ms 54184 KB Output is correct
11 Correct 7905 ms 60148 KB Output is correct
12 Correct 1890 ms 15960 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 55 ms 6080 KB Output is correct
3 Correct 39 ms 6100 KB Output is correct
4 Correct 39 ms 6360 KB Output is correct
5 Correct 40 ms 5052 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 2121 ms 27760 KB Output is correct
8 Correct 2100 ms 27404 KB Output is correct
9 Correct 36 ms 6352 KB Output is correct
10 Correct 1820 ms 24648 KB Output is correct
11 Correct 1730 ms 23692 KB Output is correct
12 Correct 699 ms 10704 KB Output is correct
13 Correct 684 ms 8400 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 55 ms 6080 KB Output is correct
3 Correct 39 ms 6100 KB Output is correct
4 Correct 39 ms 6360 KB Output is correct
5 Correct 40 ms 5052 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 7743 ms 58300 KB Output is correct
8 Correct 7711 ms 58288 KB Output is correct
9 Correct 35 ms 6104 KB Output is correct
10 Correct 7741 ms 61116 KB Output is correct
11 Correct 8022 ms 61172 KB Output is correct
12 Correct 8101 ms 61172 KB Output is correct
13 Correct 6986 ms 60584 KB Output is correct
14 Correct 8508 ms 58536 KB Output is correct
15 Correct 8125 ms 57780 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 8287 ms 60340 KB Output is correct
18 Correct 1955 ms 15440 KB Output is correct
19 Correct 7423 ms 57264 KB Output is correct
20 Correct 7156 ms 57260 KB Output is correct
21 Correct 1 ms 1372 KB Output is correct
22 Correct 2 ms 1368 KB Output is correct
23 Correct 7325 ms 54184 KB Output is correct
24 Correct 7905 ms 60148 KB Output is correct
25 Correct 1890 ms 15960 KB Output is correct
26 Correct 2121 ms 27760 KB Output is correct
27 Correct 2100 ms 27404 KB Output is correct
28 Correct 36 ms 6352 KB Output is correct
29 Correct 1820 ms 24648 KB Output is correct
30 Correct 1730 ms 23692 KB Output is correct
31 Correct 699 ms 10704 KB Output is correct
32 Correct 684 ms 8400 KB Output is correct
33 Correct 7886 ms 59060 KB Output is correct
34 Correct 7755 ms 58816 KB Output is correct
35 Correct 6690 ms 46780 KB Output is correct
36 Correct 1704 ms 14804 KB Output is correct
37 Correct 1789 ms 15020 KB Output is correct
38 Correct 1982 ms 16296 KB Output is correct