QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#446590 | #8525. Mercenaries | alpha1022 | WA | 165ms | 61660kb | C++14 | 3.7kb | 2024-06-17 13:38:14 | 2024-06-17 13:38:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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 a.x * b.y - a.y * b.x;
}
friend ll dot(const point &a, const point &b) {
return a.x * b.x + 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];
int main() {
scanf("%d", &n), seg.build(1, 1, n), scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
auto &[r, p, c, id] = qry[i]; scanf("%d%d%d%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("%d\n", ans[i] ? ans[i] : -1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 54392kb
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: 0
Accepted
time: 3ms
memory: 54564kb
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 1 2 1 1 2
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 7ms
memory: 54556kb
input:
3 87 42 5 69 12 82 79 10 88 45 51 40 3 18 6 5 73 100 58 41 40 88 54 5 40 98 31 63 100 3 32 13 1811 1 51 21 5318 1 32 5 2994 2 77 51 19184 2 78 60 1763 1 10 1 913 1 22 51 4057 1 2 5 385 2 50 15 989 2 65 53 1488 1 49 82 7708 2 33 90 1133 1 23 33 3388 1 92 36 9516 3 39 61 10014 2 43 55 1103 2 48 38 127...
output:
3 1 1 1 2 -1 -1 -1 2 2 -1 2 -1 1 2 2 -1 3 2 2 3 1 1 1 -1 1 1 1 3 1 -1 1 -1 1 2 1 2 1 1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 2 1 1 -1 2 -1 1 1 1 1 3 1 2 3 2 2 1 1 -1 1 1 3 1 1 1 3 2 1 1 2 1 2 1 2 1 -1 -1 -1 1 2 1 1 -1 -1 1 3 2 2
result:
ok 100 numbers
Test #4:
score: -100
Wrong Answer
time: 165ms
memory: 61660kb
input:
2 309248041 338995438 500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'