#include "squad.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
const int MAXN = 300005;
struct pi{
int first, second, idx, cnt;
bool operator<(const pi &q)const{
return make_pair(first, second) < make_pair(q.first, q.second);
}
};
lint ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
struct query{
pi V[MAXN];
int par[MAXN], N;
int revloc[MAXN];
void init(vector<pi> v){
memset(revloc, -1, sizeof(revloc));
N = sz(v);
vector<int> stk;
for(int i=0; i<sz(v); i++){
V[i + 1] = v[i];
}
for(int i=1; i<=N; i++){
while(sz(stk) >= 2 && ccw(V[stk[sz(stk) - 2]], V[stk.back()], V[i]) > 0){
stk.pop_back();
}
if(sz(stk)) par[i] = stk.back();
stk.push_back(i);
}
for(int i=1; i<=N; i++) revloc[V[i].idx] = i;
}
pair<lint, int> get(int x, int y, int n){
lint cur = -5e18;
int cnt = 0;
int pos = -1;
for(int i=n; i; i--){
lint qr = 1ll * x * V[i].first + 1ll * y * V[i].second;
if(qr > cur){
cur = qr;
cnt = 0;
pos = V[i].idx;
}
if(qr == cur) cnt += V[i].cnt;
}
if(cnt >= 2) pos = -1;
return make_pair(cur, pos);
}
}XP, YP, XS, YS;
int N;
vector<pi> v, w;
vector<pi> norm(vector<pi> v){
sort(v.begin(), v.end());
vector<pi> w;
for(int i=0; i<sz(v); ){
int e = i;
while(e < sz(v) && make_pair(v[i].first, v[i].second) == make_pair(v[e].first, v[e].second)) e++;
w.push_back({v[i].first, v[i].second, v[i].idx, e - i});
i = e;
}
return w;
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
N = sz(A);
for(int i=0; i<N; i++){
v.push_back({A[i], P[i], i, 1});
w.push_back({D[i], P[i], i, 1});
}
v = norm(v);
w = norm(w);
XP.init(v);
YP.init(w);
for(auto &i : v) i.first *= -1;
sort(v.begin(), v.end());
for(auto &i : w) i.first *= -1;
sort(w.begin(), w.end());
XS.init(v);
YS.init(w);
}
long long BestSquad(int X, int Y){
auto qr1 = XP.get(X, Y, XP.N);
auto qr2 = YP.get(X, Y, YP.N);
if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
lint ret = -5e18;
ret = max(ret, qr1.first + YP.get(X, Y, YP.revloc[qr1.second] - 1).first);
ret = max(ret, qr1.first + YS.get(-X, Y, YS.revloc[qr1.second] - 1).first);
ret = max(ret, qr2.first + XP.get(X, Y, XP.revloc[qr1.second] - 1).first);
ret = max(ret, qr2.first + XS.get(-X, Y, XS.revloc[qr1.second] - 1).first);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
5120 KB |
Output is correct |
2 |
Correct |
10 ms |
5248 KB |
Output is correct |
3 |
Correct |
352 ms |
57880 KB |
Output is correct |
4 |
Correct |
357 ms |
57860 KB |
Output is correct |
5 |
Correct |
27 ms |
8572 KB |
Output is correct |
6 |
Correct |
323 ms |
57880 KB |
Output is correct |
7 |
Correct |
330 ms |
57888 KB |
Output is correct |
8 |
Correct |
329 ms |
57880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5120 KB |
Output is correct |
2 |
Correct |
30 ms |
5632 KB |
Output is correct |
3 |
Execution timed out |
3101 ms |
57856 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
5120 KB |
Output is correct |
2 |
Correct |
10 ms |
5248 KB |
Output is correct |
3 |
Correct |
352 ms |
57880 KB |
Output is correct |
4 |
Correct |
357 ms |
57860 KB |
Output is correct |
5 |
Correct |
27 ms |
8572 KB |
Output is correct |
6 |
Correct |
323 ms |
57880 KB |
Output is correct |
7 |
Correct |
330 ms |
57888 KB |
Output is correct |
8 |
Correct |
329 ms |
57880 KB |
Output is correct |
9 |
Correct |
8 ms |
5120 KB |
Output is correct |
10 |
Correct |
30 ms |
5632 KB |
Output is correct |
11 |
Execution timed out |
3101 ms |
57856 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |