Submission #141257

#TimeUsernameProblemLanguageResultExecution timeMemory
141257imsifileOrganizing the Best Squad (FXCUP4_squad)C++17
100 / 100
1133 ms64028 KiB
#include "squad.h" #include <algorithm> #include <stdio.h> using namespace std; typedef long long lld; struct coord { lld x, y; int ix; bool operator< (const coord& c) const { if(x!=c.x) return x<c.x; return y<c.y; } } AP[1001001], DP[1001001]; int N; lld ccw(coord a, coord b, coord c){ // clockwise < 0 return (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x); } void makehull(coord *ba, vector<int> &chk, int val, vector<coord> &cvx){ cvx.clear(); for(int i=0; i<N; i++){ int sz; if(chk[ba[i].ix]==val) continue; while(1){ sz=cvx.size(); if(sz<2) break; if(ccw(cvx[sz-2], cvx[sz-1], ba[i]) < 0) break; cvx.pop_back(); } cvx.push_back(ba[i]); } } void threehull(coord *ba, vector<coord> &cvx, vector<coord> &odd, vector<coord> &even){ vector<int> chk(N,0); sort(ba, ba+N); makehull(ba, chk, 1, cvx); for(int i=cvx.size(); i--;){ if(i%2) chk[cvx[i].ix]=1; else chk[cvx[i].ix]=2; } makehull(ba, chk, 1, odd); makehull(ba, chk, 2, even); } vector<coord> Acv, Aov, Aev, Dcv, Dov, Dev; void Init(int N_, vector<int> A, vector<int> D, vector<int> P){ N=N_; for(int i=0; i<N; i++){ AP[i].ix=i, AP[i].x=A[i], AP[i].y=P[i]; DP[i].ix=i, DP[i].x=D[i], DP[i].y=P[i]; } threehull(AP, Acv, Aov, Aev); threehull(DP, Dcv, Dov, Dev); } int getfirst(lld A, lld B, vector<coord> &cvx){ if(cvx.size() == 1) return 0; int mi=0, mx=cvx.size()-2, md; while(mi<=mx){ md=(mi+mx)/2; if(cvx[md].x*A + cvx[md].y*B < cvx[md+1].x*A + cvx[md+1].y*B) mi=md+1; else mx=md-1; } return mi; } coord A1, A2, D1, D2; lld BestSquad(int X, int Y){ int ix; ix=getfirst(X, Y, Acv), A1=Acv[ix]; if(ix%2) ix=getfirst(X, Y, Aov), A2=Aov[ix]; else ix=getfirst(X, Y, Aev), A2=Aev[ix]; ix=getfirst(X, Y, Dcv), D1=Dcv[ix]; if(ix%2) ix=getfirst(X, Y, Dov), D2=Dov[ix]; else ix=getfirst(X, Y, Dev), D2=Dev[ix]; if(A1.ix != D1.ix) return (A1.x+D1.x)*X + (A1.y+D1.y)*Y; return max((A2.x+D1.x)*X + (A2.y+D1.y)*Y, (A1.x+D2.x)*X + (A1.y+D2.y)*Y); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...