QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446199 | #8525. Mercenaries | ucup-team3924 | WA | 0ms | 3792kb | C++20 | 5.6kb | 2024-06-17 00:48:30 | 2024-06-17 00:48:30 |
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++]);
if(j < m && b[j] == a[i])continue;
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;
Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
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]);
//}
//}
bool check(const pt &p, const Line &L){
return ((long long)p.x * L.a + (long long)p.y * L.b) >= L.c;
}
const vector<pt>org = {pt{0, 0}};
struct SegTree{
vector<vector<pt>> items; int n;
vector<vector<pt>> merc;
SegTree(int n) : merc(2*n, org), items(2 * n, org), n(n){}
void build_items(){
for(int i = n - 1; i >= 0; i--){
if(i + 1 >= n)items[i] = items[2*i+1];
else items[i] = minkowski(items[2*i + 1], items[2*i + 2]);
}
}
void build_merc(){
for(int i = n - 1; i >= 0; i--){
if(i + 1 >= n)merc[i] = merc[2*i+1];
else merc[i] = convexHull(merge(minkowski(merc[2 * i + 1], items[2 * i + 2]), merc[2* i + 2]), true);
}
}
vector<pt> sum(int b, int e) {
vector<pt>r1 = org, r2 = org;
for(b += n, e += n; b < e; b /= 2, e /= 2){
if(b%2 == 0) r1 = minkowski(r1, items[b++]);
if(e%2 == 0) r2 = minkowski(items[--e], r2);
}
return minkowski(r1, r2);
}
int solve(int city, pt shift, Line L, int v, int tl, int tr, int l, int r){
//cout << v << ' ' << l << ' ' << r << '\n';
if(l > r)return -1;
if(l == tl && r == tr){
if(!check(bestie(merc[v], L) + shift, L)){
//cout << "current shift is " << shift.x << ' ' << shift.y << '\n';
//cout << "available mercenaries are: ";
//for(auto p : merc[v])cout << p.x << ' ' << p.y << '\t';
//cout << "\nno mercenary in " << l << ' ' << r << " can beat the monster\n";
return -1;
}
if(tl == tr)return tl;
}
int tm = (tl + tr)/2;
int right = solve(city, shift, L, v * 2 + 2, tm+1, tr, max(l, tm+1), r);
if(right != -1)return right;
//cout << "there is no mercenary in " << max(l, tm + 1) << ' ' << r << " that can win so i need to remove items: ";
//cout << "the interval is " << max(l, tm+1) << ' ' << r << '\n';
//for(auto x : sum(max(l, tm+1), r+1))cout << x.x << ' ' << x.y << '\t';
//cout << '\n';
shift = shift + bestie(sum(max(l, tm+1), r+1), L);
return solve(city, shift, L, v*2+1, tl, tm, l, min(r, tm));
}
};
SegTree tree(0);
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
tree = SegTree(n);
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
tree.merc[n+i] = {pt{x, y}};
if(i + 1 == n)break;
int r;
cin >> r;
vector<pt> pts(r);
for(auto &p : pts){
cin >> p.x >> p.y;
}
tree.items[n+i+1]= convexHull(pts);
}
tree.build_items();
tree.build_merc();
//for(auto p : tree.sum(2,3))cout << p.x << ' ' << p.y << '\t';
//for(int i = 0; i < 6; i++){
//cout << "i = " << i << ": ";
//for(auto p : tree.merc[i])cout << p.x << ' ' << p.y << '\t';
//cout << '\n';
//}
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 = tree.solve(v, pt{0, 0}, L, 0, 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: 0ms
memory: 3528kb
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
Wrong Answer
time: 0ms
memory: 3792kb
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
output:
1 -1 1 2 1 2 1 -1 1 1
result:
wrong answer 3rd numbers differ - expected: '-1', found: '1'