Submission #945808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945808	2024-03-14T07:53:41 Z	salmon	Road Construction (JOI21_road_construction)	C++14	Compilation error	0 ms	0 KB

road_construction

#include <bits/stdc++.h>
using namespace std;

int N,K;
vector<pair<long long int,int>> v;
long long int X,Y;
long long int lst[250100];
const long long int inf = 1e18 / 2 * 2;
vector<int> wacter;
long long int plop[250100];

struct node{

    long long int s, m, e;
    int num;
    node *l,*r;
    set<int> v;

    node(long long int S, long long int E){
        s = S;
        e = E;
        m = (s + e + inf)/2 - inf / 2;
        num = 0;

        l = NULL;
        r = NULL;
    }

    void update(long long int i, int k, int p){
        if(s == e){
            num += k;
            if(p != -1){
                if(k == 1) v.insert(p);
                else v.erase(p);
            }
            return;
        }

        num += k;

        if(l == NULL){
            l = new node(s,m);
            r = new node(m + 1, e);
        }

        if(i <= m){
            l -> update(i,k,p);
        }
        else{
            r -> update(i,k,p);
        }
    }

    int query(long long int S, long long int E){
        if(S <= s && e <= E){
            return num;
        }

        int V = 0;

        if(l == NULL) return V;

        if(S <= m){
            V += l -> query(S,E);
        }
        if(m < E){
            V += r -> query(S,E);
        }
        return V;
    }

    void banana(int S, int E){
        if(S <= s && e <= E && s != e){
            if(l == NULL) return;
            if(l -> num > 0) l -> banana(S,E);
            if(r -> num > 0) r -> banana(S,E);
            return;
        }

        if(s == e){
            for(int i : v){
                wacter.push_back(i);
            }
            return;
        }

        int V = 0;

        if(l == NULL) return;

        if(S <= m){
            l -> banana(S,E);
        }
        if(m < E){
            r -> banana(S,E);
        }
    }

}*root;

int main(){

    scanf(" %d",&N);
    scanf(" %d",&K);

    for(int i = 0; i < N; i++){
        scanf(" %lld",&X);
        scanf(" %lld",&Y);

        v.push_back({X - Y,i});
        lst[i] = X + Y;
        plop[i] = X - Y;
    }

    v.push_back({1e16,-1});

    sort(v.begin(),v.end());

    long long int s = 0;
    long long int e = 5e9;

    while(s != e){
        long long int m = (s + e)/2;

        root = new node(0,2e10);

        int num = 0;
        int it1 = 0;
        int it2 = 0;

        for(int i = 0; i < N; i++){
            while(v[it1].first + m < v[i].first){
                root -> update(lst[v[it1].second],-1,-1);
                it1++;
            }
            while(v[i].first + m >= v[it2].first){
                root -> update(lst[v[it2].second],1,-1);
                it2++;
            }
            num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
        }

        if(num / 2 >= K){
            e = m;
        }
        else{
            s = m + 1;
        }
    }
//printf("%d",s);
    map<long long int,int> mep;

    int it1 = 0;
    int it2 = 0;

    root = new node(-2e10,2e10);

    for(int i = 0; i < N; i++){
        while(v[i].first + s >= v[it2].first){
            root -> update(lst[v[it2].second],1,v[it2].second);
            it2++;
        }
        while(v[it1].first + s < v[i].first){
            root -> update(lst[v[it1].second],-1,v[it1].second);
            it1++;
        }
        root -> banana(lst[v[i].second] - s, lst[v[i].second] + s);

        for(int j : wacter){
            mep[max(abs(lst[j] - lst[v[i].second]) , abs(plop[j] - plop[v[i].second]) ) ]++;
        }

        wacter.clear();
    }

    vector<long long int> print;

    mep.erase(0);

    for(pair<long long int, int> ii : mep){
        pair<long long int, int> temp = ii;
        for(; K > 0 && temp.second > 0; K--, temp.second -= 2){
            print.push_back(temp.first);
        }
    }

    for(long long int i : print){
        printf("%lld\n",i);
    }
}
/*
5 1
1 -1
2 0
-1 0
0 2
0 -2
*/

Compilation message

road_construction.cpp: In member function 'void node::banana(int, int)':
road_construction.cpp:87:13: warning: unused variable 'V' [-Wunused-variable]
   87 |         int V = 0;
      |             ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:140:60: error: no matching function for call to 'max(int, long long int)'
  140 |             num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
      |                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
road_construction.cpp:140:60: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  140 |             num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
      |                                                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
road_construction.cpp:140:60: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  140 |             num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
road_construction.cpp:140:60: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  140 |             num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
      |                                                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
road_construction.cpp:140:60: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  140 |             num += root -> query(max(0,lst[v[i].second] - m), lst[v[i].second] + m) - 1;
      |                                                            ^
road_construction.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
road_construction.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf(" %lld",&X);
      |         ~~~~~^~~~~~~~~~~~
road_construction.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf(" %lld",&Y);
      |         ~~~~~^~~~~~~~~~~~