oj.uz

Submission #762624

# Submission time Handle Problem Language Result Execution time Memory
762624 2023-06-21T14:51:04 Z goodbyehanbyeol Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 3000 ms 311576 KB 
#include "squad.h"
#include <bits/stdc++.h>
#define mabs(x) ((x)>0?(x):(-x))

using namespace std;

typedef long long ll;

ll gcd(ll x, ll y){
    if(!y) return x;
    return gcd(y, x%y);
}

struct Frac{
    ll a, b;
    Frac(){a=0, b=1;}
    Frac(ll x){
        a=x, b=1;
    }
    Frac(ll _a, ll _b){
        a = _a, b = _b;
        if(b<0) a=-a,b=-b;
        ll g = gcd(mabs(a), mabs(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{
        assert(r.a != a);
        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;
        }));
//        printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
//               it.get(x).a, it.get(x).b, it.idx);
        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){
    ll X = _X, Y = _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, (long long)((atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y));
    if(A1 != D2) ret = max(ret, (long long)((atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y));
    if(A2 != D1) ret = max(ret, (long long)((atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y));
    if(A2 != D2) ret = max(ret, (long long)((atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y));
    return ret;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 73020 KB Output is correct
2 Correct 38 ms 73428 KB Output is correct
3 Execution timed out 3081 ms 202932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 73044 KB Output is correct
2 Correct 59 ms 74012 KB Output is correct
3 Runtime error 1888 ms 311576 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 73020 KB Output is correct
2 Correct 38 ms 73428 KB Output is correct
3 Execution timed out 3081 ms 202932 KB Time limit exceeded
4 Halted 0 ms 0 KB -