#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 time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
286 ms |
22668 KB |
Output is correct |
4 |
Correct |
287 ms |
22768 KB |
Output is correct |
5 |
Correct |
19 ms |
4208 KB |
Output is correct |
6 |
Correct |
318 ms |
61652 KB |
Output is correct |
7 |
Correct |
371 ms |
61620 KB |
Output is correct |
8 |
Correct |
319 ms |
61596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
493 ms |
25084 KB |
Output is correct |
4 |
Correct |
434 ms |
25092 KB |
Output is correct |
5 |
Correct |
24 ms |
2300 KB |
Output is correct |
6 |
Correct |
892 ms |
43996 KB |
Output is correct |
7 |
Correct |
722 ms |
44016 KB |
Output is correct |
8 |
Correct |
719 ms |
44016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
286 ms |
22668 KB |
Output is correct |
4 |
Correct |
287 ms |
22768 KB |
Output is correct |
5 |
Correct |
19 ms |
4208 KB |
Output is correct |
6 |
Correct |
318 ms |
61652 KB |
Output is correct |
7 |
Correct |
371 ms |
61620 KB |
Output is correct |
8 |
Correct |
319 ms |
61596 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
493 ms |
25084 KB |
Output is correct |
12 |
Correct |
434 ms |
25092 KB |
Output is correct |
13 |
Correct |
24 ms |
2300 KB |
Output is correct |
14 |
Correct |
892 ms |
43996 KB |
Output is correct |
15 |
Correct |
722 ms |
44016 KB |
Output is correct |
16 |
Correct |
719 ms |
44016 KB |
Output is correct |
17 |
Correct |
79 ms |
2888 KB |
Output is correct |
18 |
Correct |
6 ms |
636 KB |
Output is correct |
19 |
Correct |
477 ms |
25020 KB |
Output is correct |
20 |
Correct |
481 ms |
24992 KB |
Output is correct |
21 |
Correct |
37 ms |
3060 KB |
Output is correct |
22 |
Correct |
1124 ms |
63896 KB |
Output is correct |
23 |
Correct |
1111 ms |
64028 KB |
Output is correct |
24 |
Correct |
1133 ms |
63860 KB |
Output is correct |