Submission #1172907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172907		abcdxyz123	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	543 ms	59780 KiB

squad

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define maxn 300005
#define inf 1000000000000000000
#define pi pair<int,int>
#define pl pair<ll,int>
#define fi first
#define se second
using namespace std;
int n;
struct point
{
    ll x,y;
    int id;
    point(ll _x=0,ll _y=0,int _id=0)
    {
        x=_x;
        y=_y;
        id=_id;
    }
};
point operator + (point A,point B)
{
    return point(A.x+B.x,A.y+B.y);
}
point operator - (point A,point B)
{
    return point(A.x-B.x,A.y-B.y);
}
ll dot(point A,point B)
{
    return A.x*B.x+A.y*B.y;
}
ll cross(point A,point B)
{
    return A.x*B.y-A.y*B.x;
}
struct
{
    vector<point>tt;
    vector<point>convex1;
    vector<point>convex2;
    vector<point>buildConvex(vector<point>&cur)
    {
        if(cur.empty())return cur;
        sort(all(cur),[](point A,point B)
        {
            if(A.x!=B.x)return A.x<B.x;
            return A.y>B.y;
        });
        vector<point>tmp;
        tmp.push_back(cur[0]);
        for(int i=1; i<(int)cur.size(); i++)
        {
            if(cur[i-1].x!=cur[i].x)
            {
                tmp.push_back(cur[i]);
            }
        }
        vector<point>convex;
        if(tmp.size()>=1)convex.push_back(tmp[0]);
        if(tmp.size()>=2)convex.push_back(tmp[1]);
        if(tmp.size()>=3)
        {
            for(int i=2; i<tmp.size(); i++)
            {
                while(convex.size()>=2&&
                        cross(tmp[i]-convex[convex.size()-1],convex[convex.size()-2]-convex[convex.size()-1])>=0)
                {
                    convex.pop_back();
                }
                convex.push_back(tmp[i]);
            }
        }
        return convex;
    }
    int nho[maxn];
    void init()
    {
        convex1=buildConvex(tt);
        for(int i=0;i<n;i++)nho[i]=0;
        for(auto[x,y,id]:convex1)nho[id]=1;
        convex2.clear();
        for(auto[x,y,id]:tt)
        {
            if(!nho[id])
            {
                convex2.push_back(point(x,y,id));
            }
        }
        convex2=buildConvex(convex2);

    }
    ll f1(int A,int B,int id)
    {
        if(id==-1)return 0;
        return A*convex1[id].x+B*convex1[id].y;
    }
    pi Find1(int A,int B)
    {
        int lo=0;
        int hi=convex1.size()-1;
        for(int t=0; t<=100; t++)
        {
            int x1=lo+(hi-lo)/3;
            int x2=hi-(hi-lo)/3;
            if(hi-lo<=5)break;
            if(f1(A,B,x1)<f1(A,B,x2))
            {
                lo=x1;
            }
            else if(f1(A,B,x1)>f1(A,B,x2))
            {
                hi=x2;
            }
            else
            {
                lo=x1;
                hi=x2;
            }
        }
        ll val1=0;int p1=-1;
        ll val2=0;int p2=-1;
        for(int i=lo; i<=hi; i++)
        {
            ll cur=f1(A,B,i);
            if(val1<=cur)
            {
                val2=val1;
                p2=p1;
                val1=cur;
                p1=i;
            }
            else if(val2<=cur)
            {
                val2=cur;
                p2=i;
            }
        }
        return {p1,p2};
    }
    ll f2(int A,int B,int id)
    {
        if(id==-1)return 0;
        return A*convex2[id].x+B*convex2[id].y;
    }
    int Find2(int A,int B)
    {
        int lo=0;
        int hi=convex2.size()-1;
        while(true)
        {
            int x1=lo+(hi-lo)/3;
            int x2=hi-(hi-lo)/3;
            if(hi-lo<=5)break;
            if(f2(A,B,x1)<f2(A,B,x2))
            {
                lo=x1;
            }
            else if(f2(A,B,x1)>f2(A,B,x2))
            {
                hi=x2;
            }
            else
            {
                lo=x1;
                hi=x2;
            }
        }
        ll val1=0;int p1=-1;
        for(int i=lo; i<=hi; i++)
        {
            ll cur=f2(A,B,i);
            if(val1<=cur)
            {
                val1=cur;
                p1=i;
            }
        }
        return p1;
    }
    void Add_Pair(int X,int Y,int id)
    {
        tt.push_back(point(X,Y,id));
    }
}AP,DP;

void Init(vector<int>A,vector<int>D,vector<int>P)
{
    n=A.size();
    for(int i=0;i<n;i++)
    {
        AP.Add_Pair(A[i],P[i],i);
        DP.Add_Pair(D[i],P[i],i);
    }
    AP.init();
    DP.init();

}
ll BestSquad(int X, int Y)
{
    pi CandAp=AP.Find1(X,Y);
    int CandAp2=AP.Find2(X,Y);
    pi CandDp=DP.Find1(X,Y);
    int CandDp2=DP.Find2(X,Y);
    //cout<<CandAp.fi<<' '<<CandAp.se<<' '<<CandAp2<<'\n';
    //cout<<CandDp.fi<<' '<<CandDp.se<<' '<<CandDp2<<'\n';
    //cout<<AP.convex1[CandAp.fi].id<<' '<<AP.convex1[CandAp.se].id<<'\n';
    //cout<<DP.convex1[CandDp.fi].id<<' '<<DP.convex1[CandDp.se].id<<'\n';
    ll ans=0;
    if(AP.convex1[CandAp.fi].id!=DP.convex1[CandDp.fi].id)
    {

        ans=AP.f1(X,Y,CandAp.fi)+DP.f1(X,Y,CandDp.fi);
    }
    else
    {
        ans=max(ans,AP.f1(X,Y,CandAp.fi)+DP.f1(X,Y,CandDp.se));
        ans=max(ans,AP.f1(X,Y,CandAp.fi)+DP.f2(X,Y,CandDp2));

        ans=max(ans,DP.f1(X,Y,CandDp.fi)+AP.f1(X,Y,CandAp.se));
        ans=max(ans,DP.f1(X,Y,CandDp.fi)+AP.f2(X,Y,CandAp2));
    }
    return ans;
}
/*

2
3 1 2
1 1 2
1
1 1


4
1 3 1
3 1 3
1 2 1
3 2 2

3
3 4
2 5
3 3

*/
/*
static int N, Q;
static std::vector<int> Att, Def, Pop;

static void my_assert(int TF, const char* message){
	if(!TF){ puts(message); exit(1); }
}

int main(){
	my_assert(scanf("%d", &N) == 1, "Error: Invalid Input");
	my_assert(2 <= N && N <= 1000000, "Error: Invalid Input");

	Att.resize(N); Def.resize(N); Pop.resize(N);
	for(int i = 0; i < N; i++){
		my_assert(scanf("%d%d%d", &Att[i], &Def[i], &Pop[i]) == 3, "Error: Invalid Input");
		my_assert(1 <= Att[i] && Att[i] <= 1000000000, "Error: Invalid Input");
		my_assert(1 <= Def[i] && Def[i] <= 1000000000, "Error: Invalid Input");
		my_assert(1 <= Pop[i] && Pop[i] <= 1000000000, "Error: Invalid Input");
	}
	Init(Att, Def, Pop);

	my_assert(scanf("%d", &Q) == 1, "Error: Invalid Input");
	my_assert(1 <= Q && Q <= 1000000, "Error: Invalid Input");

	for(int i = 0; i < Q; i++){
		int X, Y;
		my_assert(scanf("%d%d", &X, &Y) == 2, "Error: Invalid Input");
		my_assert(1 <= X && X <= 1000000000, "Error: Invalid Input");
		my_assert(1 <= Y && Y <= 1000000000, "Error: Invalid Input");
		printf("%lld\n", BestSquad(X, Y));
	}
	return 0;
}
*/

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53