QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446604#8525. MercenariesKevin5307RE 0ms0kbC++233.8kb2024-06-17 13:53:062024-06-17 13:53:07

Judging History

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

  • [2024-06-17 13:53:07]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-06-17 13:53:06]
  • 提交

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

output:


result: