QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446067 | #8525. Mercenaries | ucup-team3924 | RE | 1ms | 3552kb | C++14 | 5.1kb | 2024-06-16 20:53:11 | 2024-06-16 20:53:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct pt{
long long x, y;
bool operator<(const pt & p) const {
return tie(x, y) < tie(p.x, p.y);
}
bool operator==(const pt & p) const {
return tie(x,y) == tie(p.x, p.y);
}
pt operator + (const pt & p) const {
return pt{x + p.x, y + p.y};
}
pt operator - (const pt & p) const {
return pt{x - p.x, y - p.y};
}
long long cross(const pt & p) const {
return x * p.y - y * p.x;
}
long long cross(const pt & a, const pt & b) const{
return (a-*this).cross(b-*this);
}
};
long long det(const pt &a, const pt &b, const pt &c){
return a.cross(b, c);
}
int sgn(long long d){
return (d > 0) - (d < 0);
}
struct Line {
int a, b; long long c;
};
bool half(Line m){return m.a < 0 || (m.a == 0 && m.b < 0);};
bool operator<(Line m, Line n){
return make_pair(half(m), (long long)m.b * n.a) <
make_pair(half(n), (long long)m.a * n.b);
}
Line LineFromPoints(int x1, int y1, int x2, int y2) {
int a = y1 - y2, b = x2 - x1;
long long c = (long long)a * x1 + (long long)b * y1;
return {a, b, c}; // halfplane points to the l e f t of vec .
}
vector<pt>minkowski(const vector<pt> &P, const vector<pt> &Q){
int n = P.size(), m = Q.size();
vector<pt>res = {P[0] + Q[0]};
for(int i = 1, j = 1; i < n || j < m; ){
if(i < n && (j == m ||
(P[i] - P[i-1]).cross(Q[j] - Q[j-1]) < 0)){
res.push_back(res.back() + P[i] - P[i-1]);
++i;
} else {
res.push_back(res.back() + Q[j] - Q[j-1]);
++j;
}
}
return res;
}
vector<pt> merge(const vector<pt> &a, const vector<pt> &b){
vector<pt> res;
int n = a.size(), m = b.size();
int j = 0;
for(int i = 0; i < n; i++){
while(j < m && b[j] < a[i])res.push_back(b[j++]);
res.push_back(a[i]);
}
while(j < m)res.push_back(b[j++]);
return res;
}
vector<pt>convexHull(vector<pt> P, bool sorted=false){
if(!sorted)sort(P.begin(), P.end());
P.erase(unique(P.begin(), P.end()), P.end());
if(P.size() <= 1)return P;
vector<pt>ret;
for(auto p : P){
while(ret.size() > 0 && p.y >= ret.back().y)ret.pop_back();
while(ret.size() >= 2 && sgn(det(ret.end()[-2], ret.end()[-1], p)) > 0)ret.pop_back();
ret.push_back(p);
}
return ret;
}
pt bestie(const vector<pt> &hull, Line L){
int l = 0, r = hull.size()-1;
while(l <= r){
int m = (l + r)/2;
//cout << "checking m = " << m << '\t';
Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
//cout << (M < L) << '\n';
if(M < L)r = m - 1;
else l = m + 1;
}
return hull[(l >= (int)hull.size()? l - 1: l)];
}
vector<vector<pt>> items;
vector<vector<pt>> merc;
int n;
void build_items(const vector<vector<pt>>&hulls, int v, int tl, int tr){
if(tl == tr){
items[v] = hulls[tl];
} else {
int tm = (tl + tr)/2;
build_items(hulls, v*2, tl, tm);
build_items(hulls, v*2 + 1, tm + 1, tr);
items[v] = minkowski(items[v*2], items[v*2 + 1]);
}
}
vector<pt> sum(int v, int tl, int tr, int l, int r) {
if (l > r){
return {pt{0,0}};
}
if (l == tl && r == tr) {
return items[v];
}
int tm = (tl + tr) / 2;
return minkowski(sum(v*2, tl, tm, l, min(r, tm)),
sum(v*2+1, tm+1, tr, max(l, tm+1), r));
}
void build_merc(const vector<pt>&mercenaries, int v, int tl, int tr){
if(tl == tr){
merc[v] = {mercenaries[tl]};
} else {
int tm = (tl + tr)/2;
build_merc(mercenaries, v*2, tl, tm);
build_merc(mercenaries, v*2 + 1, tm + 1, tr);
merc[v] = convexHull(merge(minkowski(merc[v*2], items[v*2 + 1]), merc[v*2+1]));
}
}
vector<pt>naj(int v, int tl, int tr, int l, int r){
if(l > r){
return {pt{0,0}};
}
if(l == tl && r == tr){
return merc[v];
}
int tm = (tl + tr)/2;
return convexHull(merge(minkowski(naj(v*2, tl, tm, l, min(r, tm)), sum(v*2+1, tm+1, tr, max(l, tm+1), r)), naj(v*2 + 1, tm + 1, tr, max(l, tm+1), r)), true);
}
bool check(pt p, Line L){
return ((long long)p.x * L.a + (long long)p.y * L.b) >= L.c;
}
int solve(int city, pt shift, Line L, int v, int tl, int tr, int l, int r){
if(l > r){
return -1;
}
if(l == tl && r == tr){
if(!check(bestie(merc[v], L) + shift, L)){
return -1;
}
if(tl == tr)return tl;
}
int tm = (tl + tr)/2;
int right = solve(city, shift, L, v*2+1, tm+1, tr, max(l, tm+1), r);
if(right != -1)return right;
shift = shift + bestie(sum(v*2 + 1, tm + 1, tr, max(l, tm+1), r), L);
return solve(city, shift, L, v*2, tl, tm, l, min(r, tm));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
vector<pt> mercenaries(n);
vector<vector<pt>>hulls(n, {pt{0,0}});
for(int i = 0; i < n; i++){
cin >> mercenaries[i].x >> mercenaries[i].y;
if(i + 1 == n)break;
int r;
cin >> r;
vector<pt> pts(r);
for(auto &p : pts){
cin >> p.x >> p.y;
}
hulls[i + 1] = convexHull(pts);
}
while(__builtin_popcount(n) == 1)n++;
items.assign(2 * n, {pt{0, 0}});
merc.assign(2 * n + 1, {});
build_items(hulls, 1, 0, n-1);
build_merc(mercenaries, 1, 0, n-1);
int q;
cin >> q;
while(q--){
int v; int a, b;
long long c;
cin >> v >> a >> b >> c;
Line L{a, b, c};
int ans = solve(v, pt{0, 0}, L, 1, 0, n-1, 0, v-1);
cout << (ans == -1? -1 : ans + 1) << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
input:
3 1 1 2 1 2 1 2 3 2 5 1 5 4 3 3 4 5 1 1 2 4 5 12 1 1 1 1 2 1 1 1 3 1 1 1 3 1 1 9 3 2 2 20 3 1 2 18 3 1 2 19 3 1 2 20 3 0 1 8 2 1 0 4 2 1 0 3 2 1 0 2
output:
1 2 3 3 2 2 1 -1 1 -1 2 2
result:
ok 12 numbers
Test #2:
score: -100
Runtime Error
input:
2 47 11 1 98 25 9 90 10 1 32 28 1811 2 17 44 4114 1 36 88 2661 2 79 33 3681 1 53 26 2778 2 59 20 2332 2 63 45 4616 2 72 11 10835 1 13 28 919 2 16 59 4445