QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446604 | #8525. Mercenaries | Kevin5307 | RE | 0ms | 0kb | C++23 | 3.8kb | 2024-06-17 13:53:06 | 2024-06-17 13:53:07 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
struct point {
int x, y;
point(int x = 0, int y = 0) : x(x), y(y) {}
friend bool operator<(const point &a, const point &b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
friend point operator+(const point &a, const point &b) {
return point(a.x + b.x, a.y + b.y);
}
friend point operator-(const point &a, const point &b) {
return point(a.x - b.x, a.y - b.y);
}
point &operator+=(const point &o) { return *this = *this + o; }
point &operator-=(const point &o) { return *this = *this - o; }
friend ll cross(const point &a, const point &b) {
return (ll)a.x * b.y - (ll)a.y * b.x;
}
friend ll dot(const point &a, const point &b) {
return (ll)a.x * b.x + (ll)a.y * b.y;
}
};
vector<point> convexHull(vector<point> a) {
if (a.empty()) return {};
if (!is_sorted(a.begin(), a.end())) sort(a.begin(), a.end());
vector<point> ret;
for (auto i : a) {
for (; ret.size() > 1 && cross(ret.back() - ret[ret.size() - 2], i - ret.back()) >= 0; ret.pop_back());
ret.push_back(i);
}
return ret;
}
vector<point> operator*(vector<point> a, vector<point> b) {
if (a.empty() || b.empty()) return {};
vector<point> ret(a.size() + b.size() - 1);
adjacent_difference(a.begin(), a.end(), a.begin()),
adjacent_difference(b.begin(), b.end(), b.begin()),
ret[0] = a[0] + b[0],
merge(a.begin() + 1, a.end(), b.begin() + 1, b.end(), ret.begin() + 1, [&](const point &a, const point &b) {
return cross(a, b) < 0;
}),
partial_sum(ret.begin(), ret.end(), ret.begin());
return ret;
}
vector<point> operator+(vector<point> a, vector<point> b) {
if (a.empty()) return b;
if (b.empty()) return a;
vector<point> c(a.size() + b.size());
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
return convexHull(c);
}
const int N = 2e5;
int n;
struct SegmentTree {
#define ls (u << 1)
#define rs (ls | 1)
struct node {
vector<point> f, g;
int i, j;
ll fEval(point p) {
for (; i + 1 < f.size() && dot(f[i + 1] - f[i], p) > 0; ++i);
return dot(f[i], p);
}
ll gEval(point p) {
for (; j + 1 < g.size() && dot(g[j + 1] - g[j], p) > 0; ++j);
return dot(g[j], p);
}
} seg[N * 4 + 5];
void build(int u, int tl, int tr) {
if (tl == tr) {
if (tl > 1) {
int k; scanf("%d", &k); vector<point> vec(k);
for (auto &i : vec) scanf("%d%d", &i.x, &i.y);
seg[u].g = convexHull(vec);
} else seg[u].g = {{0, 0}};
int x, y; scanf("%d%d", &x, &y), seg[u].f = {{x, y}};
return ;
}
int mid = (tl + tr) >> 1;
build(ls, tl, mid), build(rs, mid + 1, tr),
seg[u].f = seg[ls].f * seg[rs].g + seg[rs].f,
seg[u].g = seg[ls].g * seg[rs].g;
}
int query(int r, point p, ll &c, int u, int tl, int tr) {
if (r >= tr) {
if (seg[u].fEval(p) < c) { c -= seg[u].gEval(p); return 0; }
if (tl == tr) return tl;
}
int mid = (tl + tr) >> 1;
int ret = 0;
if (r > mid && (ret = query(r, p, c, rs, mid + 1, tr))) return ret;
if (ret = query(r, p, c, ls, tl, mid)) return ret;
return 0;
}
#undef ls
#undef rs
} seg;
int m, ans[N + 5];
tuple<int, point, ll, int> qry[N + 5];
signed main() {
scanf("%lld", &n), seg.build(1, 1, n), scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
auto &[r, p, c, id] = qry[i]; scanf("%lld%lld%lld%lld", &r, &p.x, &p.y, &c), id = i;
}
sort(qry + 1, qry + m + 1, [&](const auto &a, const auto &b) {
return cross(get<1>(a), get<1>(b)) < 0;
});
for (int i = 1; i <= m; ++i) {
auto [r, p, c, id] = qry[i];
ans[id] = seg.query(r, p, c, 1, 1, n);
}
for (int i = 1; i <= m; ++i) printf("%lld\n", ans[i] ? ans[i] : -1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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