#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=301000;
struct point {
ll x,y;
point() {}
point(ll x,ll y):x(x),y(y) {}
};
point operator + (const point &a, const point &b) {
return point(a.x+b.x,a.y+b.y);
}
point operator - (const point &a, const point &b) {
return point(a.x-b.x,a.y-b.y);
}
bool operator < (const point &a, const point &b) {
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
vector<point> pt;
bool cmp(point a,point b,point c) {
// b在c上面
b=b-a; c=c-a;
if (b.x==c.x) return 1;
return b.y*c.x<=b.x*c.y;
}
vector<point> build(vector<point> &pt) {
int t=-1;
VI q(SZ(pt)+1,0);
rep(i,0,SZ(pt)) {
while (t>=1&&cmp(pt[q[t-1]],pt[q[t]],pt[i])) --t;
q[++t]=i;
}
vector<point> qt(t+1);
rep(i,0,t+1) qt[i]=pt[q[i]];
/*
rep(i,0,SZ(pt)) printf("%lld,%lld\n",pt[i].x,pt[i].y);
puts("---");
rep(i,0,SZ(qt)) printf("%lld,%lld\n",qt[i].x,qt[i].y);
puts("---");
*/
return qt;
}
vector<point> merge(vector<point> &pt,vector<point> &qt) {
if (pt.empty()||qt.empty()) return vector<point>(0);
vector<point> rt;
/*
rep(i,0,SZ(pt)) printf("%lld,%lld\n",pt[i].x,pt[i].y);
puts("---");
rep(i,0,SZ(qt)) printf("%lld,%lld\n",qt[i].x,qt[i].y);
puts("---");*/
rep(i,1,SZ(pt)) rt.pb(pt[i]-pt[i-1]);
rep(i,1,SZ(qt)) rt.pb(qt[i]-qt[i-1]);
sort(all(rt),[&](point &a,point &b) {
return a.x*b.y<a.y*b.x;
});
point p=pt[0]+qt[0];
// printf("faq %lld,%lld\n",p.x,p.y);
rt.insert(rt.begin(),p);
rep(i,1,SZ(rt)) rt[i]=rt[i-1]+rt[i];
// rep(i,0,SZ(rt)) printf("%lld,%lld\n",rt[i].x,rt[i].y);
// puts("----");
return rt;
}
int a[N],d[N],p[N],n;
PII pa[N],pd[N];
vector<point> ap;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n=A.size();
for(int i=0;i<n;++i) {
a[i]=A[i],d[i]=D[i],p[i]=P[i];
pa[i]=mp(a[i],i);
pd[i]=mp(d[i],i);
}
sort(pa,pa+n); sort(pd,pd+n);
rep(j,0,19) {
vector<point> pt1,pt2;
rep(i,0,n) {
int id=pa[i].se;
if (((id>>j)&1)==0) pt1.pb(point(a[id],p[id]));
}
rep(i,0,n) {
int id=pd[i].se;
if (((id>>j)&1)==1) pt2.pb(point(d[id],p[id]));
}
pt1=build(pt1); pt2=build(pt2);
pt1=merge(pt1,pt2);
for (auto p:pt1) ap.pb(p);
pt1.clear(); pt2.clear();
rep(i,0,n) {
int id=pa[i].se;
if (((id>>j)&1)==1) pt1.pb(point(a[id],p[id]));
}
rep(i,0,n) {
int id=pd[i].se;
if (((id>>j)&1)==0) pt2.pb(point(d[id],p[id]));
}
pt1=build(pt1); pt2=build(pt2);
pt1=merge(pt1,pt2);
for (auto p:pt1) ap.pb(p);
}
sort(all(ap));
ap=build(ap);
}
long long BestSquad(int X, int Y){
ll ans=0;
rep(i,0,SZ(ap)) ans=max(ans,X*ap[i].x+Y*ap[i].y);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
512 KB |
Output is correct |
| 3 |
Correct |
832 ms |
26988 KB |
Output is correct |
| 4 |
Correct |
784 ms |
28580 KB |
Output is correct |
| 5 |
Correct |
165 ms |
19160 KB |
Output is correct |
| 6 |
Execution timed out |
3104 ms |
300092 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
512 KB |
Output is correct |
| 3 |
Correct |
832 ms |
26988 KB |
Output is correct |
| 4 |
Correct |
784 ms |
28580 KB |
Output is correct |
| 5 |
Correct |
165 ms |
19160 KB |
Output is correct |
| 6 |
Execution timed out |
3104 ms |
300092 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
