Submission #762586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
762586	2023-06-21T14:14:49 Z	goodbyehanbyeol	Organizing the Best Squad (FXCUP4_squad)	C++17	Compilation error	0 ms	0 KB

squad

#include "squad.h"
#include <bits/stdc++.h>
#define mabs(x) ((x)>0?(x):(-x))

using namespace std;

typedef __int128 ll;

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll x){
        a=x, b=1;
    }
    Frac(ll _a, ll _b){
        a = _a, b = mabs(_b);
        ll g = __gcd(a, b);
        a /= g, b /= g;
    }

    Frac operator+(const Frac &r)const{
        return Frac(a*r.b+b*r.a, b*r.b);
    }

    Frac operator*(const Frac &r)const{
        return Frac(a*r.a, b*r.b);
    }

    Frac operator/(const Frac &r)const{
        return Frac(a*r.b, b*r.a);
    }

    bool operator<(Frac r)const{
        if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
        return val() < r.val();
    }

    bool operator<=(Frac r)const{
        if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
        return val() <= r.val();
    }

    bool operator==(Frac &r)const{
        return a==r.a && b==r.b;
    }

    long double val()const{
        return (long double)(a) / b;
    }
};

struct Line{
    ll a, b; Frac start; int idx;
    Line(){}
    Line(ll a, ll b): a(a), b(b){start = 0;}
    Line(ll a, ll b, int idx): a(a), b(b), idx(idx){start = 0;}
    Line(Frac start): start(start){}

    bool operator<(const Line &r)const{
        if(a == r.a) return b < r.b;
        return a < r.a;
    }

    Frac get(Frac x){
        return x*a+b;
    }

    Frac cross(Line &r)const{
        return Frac(b-r.b)/Frac(r.a-a);
    }
};

struct LineContainer{
    vector<Line> vec;
    LineContainer(){}

    void update(Line p){
        while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
        while((int)vec.size() > 1 && vec[(int)vec.size()-2].cross(p) <= vec[(int)vec.size()-2].cross(vec.back()))
            vec.pop_back();

        if(!vec.empty()) p.start = vec.back().cross(p);
        vec.push_back(p);
    }

    pair<Frac, int> query(Frac x){
        auto it = *prev(upper_bound(vec.begin(), vec.end(), Line(Frac(x)), [&](Line a, Line b){
            return a.start < b.start;
        }));
        return make_pair(it.get(x), it.idx);
    }
};

struct segmentTree{
    LineContainer tree[1<<20];

    void init(int i, int l, int r, Line *lines){
        for(int j=l; j<=r; j++) tree[i].update(lines[j]);
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m, lines);
        init(i*2+1, m+1, r, lines);
    }

    pair<Frac, int> query(int i, int l, int r, int s, int e, Frac x){
        if(r<s || e<l) return make_pair(Frac(0, 1), 0);
        if(s<=l && r<=e) return tree[i].query(x);
        int m = (l+r)>>1;
        auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
//        printf("%d %d %d %d %d %lld/%lld -> %lld/%lld (%d), %lld/%lld (%d)\n", i,l,r,s,e,x.a,x.b,p1.first.a,
//               p1.first.b,p1.second,p2.first.a,p2.first.b,p2.second);
        return max(query(i*2, l, m, s, e, x), query(i*2+1, m+1, r, s, e, x));
    }
} treeA, treeD;

int n, dcond;
ll atk[300002], def[300002], pop[300002];
Line vecA[300002], vecD[300002];
int idxA[300002], idxD[300002];

void Init(vector<int> A, vector<int> D, vector<int> P){
	n = (int)A.size(), dcond = 1;
	for(int i=1; i<=n; i++){
        atk[i] = A[i-1];
        def[i] = D[i-1];
        pop[i] = P[i-1];
        if(def[i] != 1) dcond = 0;
	}

    for(int i=1; i<=n; i++){
        vecA[i] = Line(pop[i]-atk[i], atk[i], i);
        vecD[i] = Line(pop[i]-def[i], def[i], i);
    }
    sort(vecA+1, vecA+n+1);
    sort(vecD+1, vecD+n+1);
    for(int i=1; i<=n; i++){
        idxA[vecA[i].idx] = i;
        idxD[vecD[i].idx] = i;
    }

    treeA.init(1, 1, n, vecA);
    treeD.init(1, 1, n, vecD);
}

long long BestSquad(int X, int Y){
    int A1 = treeA.query(1, 1, n, 1, n, Frac(Y, X+Y)).second;
    int A2 = max(treeA.query(1, 1, n, 1, idxA[A1]-1, Frac(Y, X+Y)),
                 treeA.query(1, 1, n, idxA[A1]+1, n, Frac(Y, X+Y))).second;
    int D1 = treeD.query(1, 1, n, 1, n, Frac(Y, X+Y)).second;
    int D2 = max(treeD.query(1, 1, n, 1, idxD[D1]-1, Frac(Y, X+Y)),
                 treeD.query(1, 1, n, idxD[D1]+1, n, Frac(Y, X+Y))).second;

    long long ret = 0;
    if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
    if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
    if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
    if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
    return ret;
}

Compilation message

squad.cpp: In member function 'std::pair<Frac, int> segmentTree::query(int, int, int, int, int, Frac)':
squad.cpp:109:14: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
  109 |         auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
      |              ^~
squad.cpp:109:46: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
  109 |         auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
      |                                              ^~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:154:82: error: no matching function for call to 'max(long long int&, ll)'
  154 |     if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:154:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  154 |     if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:154:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  154 |     if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:154:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  154 |     if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:154:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  154 |     if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
      |                                                                                  ^
squad.cpp:155:82: error: no matching function for call to 'max(long long int&, ll)'
  155 |     if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:155:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  155 |     if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:155:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  155 |     if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:155:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  155 |     if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:155:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  155 |     if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
      |                                                                                  ^
squad.cpp:156:82: error: no matching function for call to 'max(long long int&, ll)'
  156 |     if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:156:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  156 |     if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:156:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  156 |     if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:156:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  156 |     if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:156:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  156 |     if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
      |                                                                                  ^
squad.cpp:157:82: error: no matching function for call to 'max(long long int&, ll)'
  157 |     if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:157:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  157 |     if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/vector:60,
                 from squad.h:2,
                 from squad.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:
squad.cpp:157:82: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
  157 |     if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:157:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  157 |     if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
      |                                                                                  ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from squad.cpp:2:
/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:
squad.cpp:157:82: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  157 |     if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
      |                                                                                  ^