oj.uz

Submission #709994

# Submission time Handle Problem Language Result Execution time Memory
709994 2023-03-15T02:34:26 Z alvingogo Road Construction (JOI21_road_construction) C++14
100 / 100
 3524 ms 19208 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

/*

never did before, write down here

we want to find out the minimum k mahhaton dist
transform the (x, y) into (x+y, x-y)
so that |x-a|+|y-b| = max(|x'-a'|,|y'-b'|)

and binary search the k, find how many pair of points dis <= k

actually, it's like: 
maintain a single-point-modify-range-query-sum DS
scan one axis, the DS is for another axis, when we want to cal all points whose x' = z
just add the Y to the DS, and count the amount of [Y-k, Y+k], 
wow, not that hard, right?  

we need to find the 1st to kth smallest distance

find the k-th smallest distance, let it be x

for all dist<x, the sum is small enough so we can iterate all of it

let's go

*/

struct BIT{
    int n;
    vector<int> bt;
    void init(int x){
        n=x;
        bt.resize(x+1);
    }
    void update(int x,int y){
        x++;
        for(;x<=n;x+=(x&-x)){
            bt[x]+=y;
        }
    }
    int query(int x){
        int ans=0;
        x++;
        for(;x>0;x-=(x&-x)){
            ans+=bt[x];
        }
        return ans;
    }
    int ask(int l,int r){
        return query(r)-query(l-1);
    }
}bt;

signed main(){
    AquA;
    //freopen("01-03.txt","r",stdin);
    //freopen("abc.txt","w",stdout);
    int n,m;
    cin >> n >> m;
    vector<pair<int,int> > v;
    vector<int> g;
    for(int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        v.push_back({a+b,a-b});
        g.push_back(a-b);
    }
    sort(v.begin(),v.end());
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    auto lis=[&](int x){
        return lower_bound(g.begin(),g.end(),x)-g.begin();
    };
    bt.init(g.size());
    for(auto &h:v){
        h.sc=lis(h.sc);
    }
    auto cal=[&](int k){
        int z=0;
        int ans=0;
        for(int i=0;i<n;i++){
            while(z<i && v[z].fs+k<v[i].fs){
                bt.update(v[z].sc,-1);
                z++;
            }
            int l=lis(g[v[i].sc]-k),r=upper_bound(g.begin(),g.end(),g[v[i].sc]+k)-g.begin()-1;
            ans+=bt.ask(l,r);
            bt.update(v[i].sc,1);
        }
        while(z<n){
            bt.update(v[z].sc,-1);
            z++;
        }
        return ans;
    };
    int l=0,r=9e10;
    while(r>l){
        int mid=(l+r+1)/2;
        //cout << l << " " << mid << " " << r << "\n";
        //cout << cal(mid) << "\n";
        if(cal(mid)>m){
            r=mid-1;
        }
        else{
            l=mid;
        }
    }
    vector<int> ret;
    set<pair<int,int> > s;
    int z=0;
    for(int i=0;i<n;i++){
        while(z<i && v[z].fs+l<v[i].fs){
            s.erase({g[v[z].sc],v[z].fs});
            z++;
        }
        for(auto h=s.lower_bound({g[v[i].sc]-l,-3e10});h!=s.end() && ((*h).fs-l<=g[v[i].sc]);h=next(h)){
            ret.push_back(max(abs(v[i].fs-(*h).sc),abs(g[v[i].sc]-(*h).fs)));
        }
        s.insert({g[v[i].sc],v[i].fs});
    }
    sort(ret.begin(),ret.end());
    while(ret.size()<m){
        ret.push_back(l+1);
    }
    assert(ret.size()==m);
    for(auto h:ret){
        cout << h << '\n';
    }
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:130:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  130 |     while(ret.size()<m){
      |           ~~~~~~~~~~^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:1:
road_construction.cpp:133:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  133 |     assert(ret.size()==m);
      |            ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5000 KB Output is correct
2 Correct 48 ms 4952 KB Output is correct
3 Correct 51 ms 5084 KB Output is correct
4 Correct 51 ms 5160 KB Output is correct
5 Correct 47 ms 3896 KB Output is correct
6 Correct 3 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1594 ms 13364 KB Output is correct
2 Correct 1543 ms 13360 KB Output is correct
3 Correct 37 ms 4936 KB Output is correct
4 Correct 1532 ms 13228 KB Output is correct
5 Correct 1465 ms 13560 KB Output is correct
6 Correct 1488 ms 13504 KB Output is correct
7 Correct 1402 ms 12824 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2918 ms 8200 KB Output is correct
2 Correct 3026 ms 8216 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1424 ms 11076 KB Output is correct
5 Correct 985 ms 13580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2918 ms 8200 KB Output is correct
2 Correct 3026 ms 8216 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1424 ms 11076 KB Output is correct
5 Correct 985 ms 13580 KB Output is correct
6 Correct 3112 ms 13272 KB Output is correct
7 Correct 2975 ms 13288 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2984 ms 13268 KB Output is correct
11 Correct 1405 ms 11164 KB Output is correct
12 Correct 936 ms 13556 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5000 KB Output is correct
2 Correct 48 ms 4952 KB Output is correct
3 Correct 51 ms 5084 KB Output is correct
4 Correct 51 ms 5160 KB Output is correct
5 Correct 47 ms 3896 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1183 ms 11612 KB Output is correct
8 Correct 1154 ms 11612 KB Output is correct
9 Correct 39 ms 5028 KB Output is correct
10 Correct 1094 ms 10760 KB Output is correct
11 Correct 1042 ms 10592 KB Output is correct
12 Correct 302 ms 11196 KB Output is correct
13 Correct 384 ms 9780 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5000 KB Output is correct
2 Correct 48 ms 4952 KB Output is correct
3 Correct 51 ms 5084 KB Output is correct
4 Correct 51 ms 5160 KB Output is correct
5 Correct 47 ms 3896 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1594 ms 13364 KB Output is correct
8 Correct 1543 ms 13360 KB Output is correct
9 Correct 37 ms 4936 KB Output is correct
10 Correct 1532 ms 13228 KB Output is correct
11 Correct 1465 ms 13560 KB Output is correct
12 Correct 1488 ms 13504 KB Output is correct
13 Correct 1402 ms 12824 KB Output is correct
14 Correct 2918 ms 8200 KB Output is correct
15 Correct 3026 ms 8216 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1424 ms 11076 KB Output is correct
18 Correct 985 ms 13580 KB Output is correct
19 Correct 3112 ms 13272 KB Output is correct
20 Correct 2975 ms 13288 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2984 ms 13268 KB Output is correct
24 Correct 1405 ms 11164 KB Output is correct
25 Correct 936 ms 13556 KB Output is correct
26 Correct 1183 ms 11612 KB Output is correct
27 Correct 1154 ms 11612 KB Output is correct
28 Correct 39 ms 5028 KB Output is correct
29 Correct 1094 ms 10760 KB Output is correct
30 Correct 1042 ms 10592 KB Output is correct
31 Correct 302 ms 11196 KB Output is correct
32 Correct 384 ms 9780 KB Output is correct
33 Correct 3386 ms 19208 KB Output is correct
34 Correct 3524 ms 19204 KB Output is correct
35 Correct 3104 ms 18056 KB Output is correct
36 Correct 913 ms 18288 KB Output is correct
37 Correct 947 ms 18308 KB Output is correct
38 Correct 1315 ms 17028 KB Output is correct