Submission #762584

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

squad

#include "squad.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long __int128;

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll x){
        a=x, b=1;
    }
    Frac(ll _a, ll _b){
        a = _a, b = abs(_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:6:19: error: declaration does not declare anything [-fpermissive]
    6 | typedef long long __int128;
      |                   ^~~~~~~~
squad.cpp:9:5: error: 'll' does not name a type
    9 |     ll a, b;
      |     ^~
squad.cpp:11:12: error: expected ')' before 'x'
   11 |     Frac(ll x){
      |         ~  ^~
      |            )
squad.cpp:14:12: error: expected ')' before '_a'
   14 |     Frac(ll _a, ll _b){
      |         ~  ^~~
      |            )
squad.cpp: In member function 'Frac Frac::operator+(const Frac&) const':
squad.cpp:21:21: error: 'a' was not declared in this scope
   21 |         return Frac(a*r.b+b*r.a, b*r.b);
      |                     ^
squad.cpp:21:25: error: 'const struct Frac' has no member named 'b'
   21 |         return Frac(a*r.b+b*r.a, b*r.b);
      |                         ^
squad.cpp:21:27: error: 'b' was not declared in this scope
   21 |         return Frac(a*r.b+b*r.a, b*r.b);
      |                           ^
squad.cpp:21:31: error: 'const struct Frac' has no member named 'a'
   21 |         return Frac(a*r.b+b*r.a, b*r.b);
      |                               ^
squad.cpp:21:38: error: 'const struct Frac' has no member named 'b'
   21 |         return Frac(a*r.b+b*r.a, b*r.b);
      |                                      ^
squad.cpp: In member function 'Frac Frac::operator*(const Frac&) const':
squad.cpp:25:21: error: 'a' was not declared in this scope
   25 |         return Frac(a*r.a, b*r.b);
      |                     ^
squad.cpp:25:25: error: 'const struct Frac' has no member named 'a'
   25 |         return Frac(a*r.a, b*r.b);
      |                         ^
squad.cpp:25:28: error: 'b' was not declared in this scope
   25 |         return Frac(a*r.a, b*r.b);
      |                            ^
squad.cpp:25:32: error: 'const struct Frac' has no member named 'b'
   25 |         return Frac(a*r.a, b*r.b);
      |                                ^
squad.cpp: In member function 'Frac Frac::operator/(const Frac&) const':
squad.cpp:29:21: error: 'a' was not declared in this scope
   29 |         return Frac(a*r.b, b*r.a);
      |                     ^
squad.cpp:29:25: error: 'const struct Frac' has no member named 'b'
   29 |         return Frac(a*r.b, b*r.a);
      |                         ^
squad.cpp:29:28: error: 'b' was not declared in this scope
   29 |         return Frac(a*r.b, b*r.a);
      |                            ^
squad.cpp:29:32: error: 'const struct Frac' has no member named 'a'
   29 |         return Frac(a*r.b, b*r.a);
      |                                ^
squad.cpp: In member function 'bool Frac::operator<(Frac) const':
squad.cpp:33:17: error: 'a' was not declared in this scope
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                 ^
squad.cpp:33:20: error: 'b' was not declared in this scope
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                    ^
squad.cpp:33:25: error: 'struct Frac' has no member named 'a'
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                         ^
squad.cpp:33:30: error: 'struct Frac' has no member named 'b'
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                              ^
squad.cpp:33:32: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                                ^
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:33:32: note:   candidate expects 2 arguments, 1 provided
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                                ^
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:33:32: note:   candidate expects 3 arguments, 1 provided
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                                ^
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:
/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:33:53: error: 'struct Frac' has no member named 'b'
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                                                     ^
squad.cpp:33:61: error: 'struct Frac' has no member named 'a'
   33 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
      |                                                             ^
squad.cpp: In member function 'bool Frac::operator<=(Frac) const':
squad.cpp:38:17: error: 'a' was not declared in this scope
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                 ^
squad.cpp:38:20: error: 'b' was not declared in this scope
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                    ^
squad.cpp:38:25: error: 'struct Frac' has no member named 'a'
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                         ^
squad.cpp:38:30: error: 'struct Frac' has no member named 'b'
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                              ^
squad.cpp:38:32: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                                ^
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:38:32: note:   candidate expects 2 arguments, 1 provided
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                                ^
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:38:32: note:   candidate expects 3 arguments, 1 provided
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                                ^
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:
/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:38:53: error: 'struct Frac' has no member named 'b'
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                                                     ^
squad.cpp:38:62: error: 'struct Frac' has no member named 'a'
   38 |         if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
      |                                                              ^
squad.cpp: In member function 'bool Frac::operator==(Frac&) const':
squad.cpp:43:16: error: 'a' was not declared in this scope
   43 |         return a==r.a && b==r.b;
      |                ^
squad.cpp:43:21: error: 'struct Frac' has no member named 'a'
   43 |         return a==r.a && b==r.b;
      |                     ^
squad.cpp:43:26: error: 'b' was not declared in this scope
   43 |         return a==r.a && b==r.b;
      |                          ^
squad.cpp:43:31: error: 'struct Frac' has no member named 'b'
   43 |         return a==r.a && b==r.b;
      |                               ^
squad.cpp: In member function 'long double Frac::val() const':
squad.cpp:47:30: error: 'a' was not declared in this scope
   47 |         return (long double)(a) / b;
      |                              ^
squad.cpp:47:35: error: 'b' was not declared in this scope
   47 |         return (long double)(a) / b;
      |                                   ^
squad.cpp: At global scope:
squad.cpp:52:5: error: 'll' does not name a type
   52 |     ll a, b; Frac start; int idx;
      |     ^~
squad.cpp:54:12: error: expected ')' before 'a'
   54 |     Line(ll a, ll b): a(a), b(b){start = 0;}
      |         ~  ^~
      |            )
squad.cpp:55:12: error: expected ')' before 'a'
   55 |     Line(ll a, ll b, int idx): a(a), b(b), idx(idx){start = 0;}
      |         ~  ^~
      |            )
squad.cpp: In member function 'bool Line::operator<(const Line&) const':
squad.cpp:59:12: error: 'a' was not declared in this scope
   59 |         if(a == r.a) return b < r.b;
      |            ^
squad.cpp:59:19: error: 'const struct Line' has no member named 'a'
   59 |         if(a == r.a) return b < r.b;
      |                   ^
squad.cpp:59:29: error: 'b' was not declared in this scope
   59 |         if(a == r.a) return b < r.b;
      |                             ^
squad.cpp:59:35: error: 'const struct Line' has no member named 'b'
   59 |         if(a == r.a) return b < r.b;
      |                                   ^
squad.cpp:60:16: error: 'a' was not declared in this scope
   60 |         return a < r.a;
      |                ^
squad.cpp:60:22: error: 'const struct Line' has no member named 'a'
   60 |         return a < r.a;
      |                      ^
squad.cpp: In member function 'Frac Line::get(Frac)':
squad.cpp:64:18: error: 'a' was not declared in this scope
   64 |         return x*a+b;
      |                  ^
squad.cpp:64:20: error: 'b' was not declared in this scope
   64 |         return x*a+b;
      |                    ^
squad.cpp: In member function 'Frac Line::cross(Line&) const':
squad.cpp:68:21: error: 'b' was not declared in this scope
   68 |         return Frac(b-r.b)/Frac(r.a-a);
      |                     ^
squad.cpp:68:25: error: 'struct Line' has no member named 'b'
   68 |         return Frac(b-r.b)/Frac(r.a-a);
      |                         ^
squad.cpp:68:35: error: 'struct Line' has no member named 'a'
   68 |         return Frac(b-r.b)/Frac(r.a-a);
      |                                   ^
squad.cpp:68:37: error: 'a' was not declared in this scope
   68 |         return Frac(b-r.b)/Frac(r.a-a);
      |                                     ^
squad.cpp: In member function 'void LineContainer::update(Line)':
squad.cpp:77:42: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'a'
   77 |         while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
      |                                          ^
squad.cpp:77:49: error: 'struct Line' has no member named 'a'
   77 |         while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
      |                                                 ^
squad.cpp:77:65: error: '__gnu_cxx::__alloc_traits<std::allocator<Line>, Line>::value_type' {aka 'struct Line'} has no member named 'b'
   77 |         while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
      |                                                                 ^
squad.cpp:77:72: error: 'struct Line' has no member named 'b'
   77 |         while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
      |                                                                        ^
squad.cpp: In member function 'std::pair<Frac, int> segmentTree::query(int, int, int, int, int, Frac)':
squad.cpp:105:50: error: no matching function for call to 'Frac::Frac(int, int)'
  105 |         if(r<s || e<l) return make_pair(Frac(0, 1), 0);
      |                                                  ^
squad.cpp:10:5: note: candidate: 'Frac::Frac()'
   10 |     Frac(){}
      |     ^~~~
squad.cpp:10:5: note:   candidate expects 0 arguments, 2 provided
squad.cpp:8:8: note: candidate: 'constexpr Frac::Frac(const Frac&)'
    8 | struct Frac{
      |        ^~~~
squad.cpp:8:8: note:   candidate expects 1 argument, 2 provided
squad.cpp:8:8: note: candidate: 'constexpr Frac::Frac(Frac&&)'
squad.cpp:8:8: note:   candidate expects 1 argument, 2 provided
squad.cpp: At global scope:
squad.cpp:116:1: error: 'll' does not name a type
  116 | ll atk[300002], def[300002], pop[300002];
      | ^~
squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:123:9: error: 'atk' was not declared in this scope
  123 |         atk[i] = A[i-1];
      |         ^~~
squad.cpp:124:9: error: 'def' was not declared in this scope
  124 |         def[i] = D[i-1];
      |         ^~~
squad.cpp:125:9: error: 'pop' was not declared in this scope; did you mean 'pow'?
  125 |         pop[i] = P[i-1];
      |         ^~~
      |         pow
squad.cpp:130:24: error: 'pop' was not declared in this scope; did you mean 'pow'?
  130 |         vecA[i] = Line(pop[i]-atk[i], atk[i], i);
      |                        ^~~
      |                        pow
squad.cpp:130:31: error: 'atk' was not declared in this scope
  130 |         vecA[i] = Line(pop[i]-atk[i], atk[i], i);
      |                               ^~~
squad.cpp:131:31: error: 'def' was not declared in this scope
  131 |         vecD[i] = Line(pop[i]-def[i], def[i], i);
      |                               ^~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:145:52: error: no matching function for call to 'Frac::Frac(int&, int)'
  145 |     int A1 = treeA.query(1, 1, n, 1, n, Frac(Y, X+Y)).second;
      |                                                    ^
squad.cpp:10:5: note: candidate: 'Frac::Frac()'
   10 |     Frac(){}
      |     ^~~~
squad.cpp:10:5: note:   candidate expects 0 arguments, 2 provided
squad.cpp:8:8: note: candidate: 'constexpr Frac::Frac(const Frac&)'
    8 | struct Frac{
      |        ^~~~
squad.cpp:8:8: note:   candidate expects 1 argument, 2 provided
squad.cpp:8:8: note: candidate: 'constexpr Frac::Frac(Frac&&)'
squad.cpp:8:8: note:   candidate expects 1 argument, 2 provided
squad.cpp:146:65: error: no matching function for call to 'Frac::Frac(int&, int)'
  146 |     int A2 = max(treeA.query(1, 1, n, 1, idxA[A1]-1, Frac(Y, X+Y)),
      |                                                                 ^
squad.cpp:10:5: note: candidate: 'Frac::Frac()'