QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#448163 | #8525. Mercenaries | hos_lyric | WA | 0ms | 4092kb | C++14 | 11.4kb | 2024-06-19 13:03:42 | 2024-06-19 13:03:42 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreePoint {
int logN, n;
vector<T> ts;
SegmentTreePoint() : logN(0), n(0) {}
explicit SegmentTreePoint(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreePoint(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Changes the value of point a to s.
template <class S> void change(int a, const S &s) {
assert(0 <= a); assert(a < n);
ts[a += n] = T(s);
for (; a >>= 1; ) pull(a);
}
// Applies T::f(args...) to point a.
template <class F, class... Args>
void ch(int a, F f, Args &&... args) {
assert(0 <= a); assert(a < n);
(ts[a += n].*f)(args...);
for (; a >>= 1; ) pull(a);
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
T prodL, prodR, t;
for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
if (a & 1) { t.pull(prodL, ts[a++]); prodL = t; }
if (b & 1) { t.pull(ts[--b], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
auto prodL = e(), prodR = e();
for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
if (a & 1) prodL = op(prodL, (ts[a++].*f)(args...));
if (b & 1) prodR = op((ts[--b].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
}; // SegmentTreePoint<T>
////////////////////////////////////////////////////////////////////////////////
inline int sig(Int r) { return (r < 0) ? -1 : (r > 0) ? +1 : 0; }
inline Int sq(Int r) { return r * r; }
struct Pt {
Int x, y;
Pt() : x(0), y(0) {}
Pt(Int x_, Int y_) : x(x_), y(y_) {}
Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
Pt operator+() const { return Pt(+x, +y); }
Pt operator-() const { return Pt(-x, -y); }
Pt operator*(const Int &k) const { return Pt(x * k, y * k); }
Pt operator/(const Int &k) const { return Pt(x / k, y / k); }
friend Pt operator*(const Int &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
Pt &operator*=(const Pt &a) { return *this = *this * a; }
Pt &operator*=(const Int &k) { x *= k; y *= k; return *this; }
Int abs2() const { return x * x + y * y; }
Int dot(const Pt &a) const { return x * a.x + y * a.y; }
Int det(const Pt &a) const { return x * a.y - y * a.x; }
bool operator==(const Pt &a) const { return (x == a.x && y == a.y); }
bool operator<(const Pt &a) const { return ((x != a.x) ? (x < a.x) : (y < a.y)); }
friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
};
inline Int tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
// [0, 2 PI)
int cmpArg(const Pt &a, const Pt &b) {
const int sa = (a.y > 0) ? 1 : (a.y < 0) ? 3 : (a.x > 0) ? 0 : 2;
const int sb = (b.y > 0) ? 1 : (b.y < 0) ? 3 : (b.x > 0) ? 0 : 2;
return (sa < sb) ? -1 : (sa > sb) ? +1 : sig(b.det(a));
}
vector<Pt> convexHull(vector<Pt> ps) {
const int n = ps.size();
sort(ps.begin(), ps.end());
vector<Pt> qs;
for (int i = 0; i < n; qs.push_back(ps[i++]))
for (; qs.size() > 1 && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
const int r = qs.size();
for (int i = (int)ps.size() - 2; i >= 0; qs.push_back(ps[i--]))
for (; (int)qs.size() > r && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
if (qs.size() > 1) qs.pop_back();
if (qs.size() == 2 && qs[0] == qs[1]) qs.pop_back();
return qs;
}
// arg(ps[1] - ps[0]) is min
void rot(vector<Pt> &ps) {
const int n = ps.size();
int im = 0;
for (int i = 0; i < n; ++i) {
if (ps[im].y > ps[i].y || (ps[im].y == ps[i].y && ps[im].x > ps[i].x)) {
im = i;
}
}
rotate(ps.begin(), ps.begin() + im, ps.end());
}
vector<Pt> add(const vector<Pt> &as, const vector<Pt> &bs) {
const int asLen = as.size();
const int bsLen = bs.size();
assert(asLen >= 1);
assert(bsLen >= 1);
if (asLen == 1) {
auto ret = bs;
for (int j = 0; j < bsLen; ++j) ret[j] += as[0];
return ret;
}
if (bsLen == 1) {
auto ret = as;
for (int i = 0; i < asLen; ++i) ret[i] += bs[0];
return ret;
}
vector<Pt> us(asLen + bsLen);
for (int i = 0; i < asLen; ++i) us[i] = as[(i + 1) % asLen] - as[i];
for (int j = 0; j < bsLen; ++j) us[asLen + j] = bs[(j + 1) % bsLen] - bs[j];
inplace_merge(us.begin(), us.begin() + asLen, us.end(), [&](const Pt &u, const Pt &v) -> bool {
return (cmpArg(u, v) < 0);
});
vector<Pt> ret(asLen + bsLen);
ret[0] = as[0] + bs[0];
for (int i = 0; i < asLen + bsLen - 1; ++i) ret[i + 1] = ret[i] + us[i];
return ret;
}
// TODO: O(n)
vector<Pt> merge(const vector<Pt> &as, const vector<Pt> &bs) {
auto cs = as;
cs.insert(cs.end(), bs.begin(), bs.end());
cs = convexHull(cs);
rot(cs);
return cs;
}
// max (a x + b y)
constexpr Int INF = 1001001001001001001LL;
Int maximize(const vector<Pt> &ps, Int a, Int b) {
const int n = ps.size();
if (n == 0) return -INF;
auto at = [&](int i) -> Int {
const Pt &p = ps[i % n];
return a * p.x + b * p.y;
};
// invariant: i < j < k && at(i) <= at(j) >= at(k)
int i = 0, j = n, k = n + n;
Int fj = at(j);
for (; i + 2 < k; ) {
const int ij = (i + j) / 2;
const int jk = (j + k + 1) / 2;
const Int fij = at(ij);
const Int fjk = at(jk);
if (fij > fj) {
j = ij; k = j;
fj = fij;
} else if (fj < fjk) {
j = jk; i = j;
fj = fjk;
} else {
i = ij; k = jk;
}
}
// cerr<<"[maximize] "<<ps<<" "<<a<<" "<<b<<": "<<j<<" "<<fj<<endl;
return fj;
}
/*
ps: hull(V[l] + ... + V[r-1])
qs: hull(U[l] + V[l] + ... + V[r-1], U[l+1] + V[l+1] + ... + V[r-1], ..., U[r-1] + V[r-1])
*/
struct Node {
vector<Pt> ps, qs;
void pull(const Node &l, const Node &r) {
if (!l.ps.size()) {
*this = r;
return;
}
if (!r.ps.size()) {
*this = l;
return;
}
ps = add(l.ps, r.ps);
qs = merge(add(l.qs, r.ps), r.qs);
}
bool test(Int a, Int b, Int &c) {
if (!ps.size()) {
return false;
}
if (maximize(qs, a, b) >= c) {
return true;
}
c -= maximize(ps, a, b);
return false;
}
};
int N;
vector<Pt> U;
vector<vector<Pt>> V;
int Q;
vector<int> I;
vector<Int> A, B, C;
int main() {
for (; ~scanf("%d", &N); ) {
U.resize(N);
V.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld%lld", &U[i].x, &U[i].y);
if (i < N - 1) {
int len;
scanf("%d", &len);
V[i].resize(len);
for (int j = 0; j < len; ++j) {
scanf("%lld%lld", &V[i][j].x, &V[i][j].y);
}
} else {
V[i] = {Pt(0, 0)};
}
}
scanf("%d", &Q);
I.resize(Q);
A.resize(Q);
B.resize(Q);
C.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%lld%lld%lld", &I[q], &A[q], &B[q], &C[q]);
--I[q];
}
for (int i = 0; i < N; ++i) {
V[i] = convexHull(V[i]);
rot(V[i]);
}
// cerr<<"U = "<<U<<endl;
// cerr<<"V = "<<V<<endl;
SegmentTreePoint<Node> seg(N);
for (int i = 0; i < N; ++i) {
seg.at(i).ps = V[i];
seg.at(i).qs = add({U[i]}, V[i]);
}
seg.build();
// for(int a=1;a<seg.n<<1;++a)cerr<<seg.ts[a].ps<<" "<<seg.ts[a].qs<<endl;
for (int q = 0; q < Q; ++q) {
Int c = C[q];
int ans;
if (A[q] * U[I[q]].x + B[q] * U[I[q]].y >= C[q]) {
// cerr<<"easy ";
ans = I[q];
} else {
ans = seg.findLeft(I[q], &Node::test, A[q], B[q], c);
}
printf("%d\n", (ans >= 0) ? (ans + 1) : -1);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4092kb
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: 0ms
memory: 3772kb
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: -100
Wrong Answer
time: 0ms
memory: 3840kb
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 1 2 -1 3 2 1 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 1 -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 1 -1 -1 1 1 1 1 2 -1 -1 -1 -1 1 2 1 1 -1 -1 1 3 2 2
result:
wrong answer 15th numbers differ - expected: '2', found: '1'