QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#448163#8525. Mercenarieshos_lyricWA 0ms4092kbC++1411.4kb2024-06-19 13:03:422024-06-19 13:03:42

Judging History

你现在查看的是最新测评结果

  • [2024-06-19 13:03:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4092kb
  • [2024-06-19 13:03:42]
  • 提交

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'