Submission #24434

#	Time	Username	Problem	Language	Result	Execution time	Memory
24434		jiaqiyang	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1049 ms	19352 KiB

dragon2

#include <cstdio>
#include <cstring>
#include <tuple>
#include <vector>
#include <algorithm>

typedef long long i64;

const int N = 100000 + 10;

int n, m;

struct Point {
  i64 x, y;
  Point() {}
  Point(i64 _x, i64 _y): x(_x), y(_y) {}
};

inline Point operator- (const Point &a, const Point &b) {
  return Point(a.x - b.x, a.y - b.y);
}

inline i64 cross(const Point &a, const Point &b) {
  return a.x * b.y - a.y * b.x;
}

inline i64 cross(const Point &o, const Point &a, const Point &b) {
  return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

inline bool operator< (const Point &a, const Point &b) {
  return cross(a, b) > 0;
}

int c[N];
bool flag[N];

Point r[N];

std::pair<int, Point> a[N];
std::pair<Point, int> b[N];

int pos[N], l[N];

Point st, ed;

std::vector<std::pair<int, int>> q, u[N], v[N];

int ans[N];

void init() {
  scanf("%d%d", &n, &m);
  static Point p[N];
  for (int i = 0; i < n; ++i) scanf("%lld%lld%d", &p[i].x, &p[i].y, &c[i]), --c[i];
  scanf("%lld%lld%lld%lld", &st.x, &st.y, &ed.x, &ed.y);
  for (int i = 0; i < n; ++i) flag[i] = cross(st, ed, p[i]) > 0;
  for (int i = 0; i < n; ++i) a[i] = {c[i], r[i] = flag[i] ? p[i] - ed : ed - p[i]};
  std::sort(a, a + n);
  for (int i = 0; i < n; ++i) pos[i] = std::lower_bound(a, a + n, std::make_pair(c[i], r[i])) - a;
  for (int i = 0; i <= m; ++i) l[i] = std::lower_bound(a, a + n, std::make_pair(i, ed - st)) - a;
  for (int i = 0; i < n; ++i) b[i] = {flag[i] ? p[i] - st : st - p[i], i};
  std::sort(b, b + n);
  int k;
  scanf("%d", &k);
  for (int i = 0; i < k; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    q.emplace_back(--x, --y);
    u[x].emplace_back(y, i);
  }
  for (int i = 0; i < m; ++i) {
    if (u[i].size() <= 300) continue;
    for (auto j : u[i]) v[j.first].emplace_back(i, j.second);
    u[i].clear();
  }
}

class BIT {
  int data[N];
  int query(int p) {
    int res = 0;
    for (++p; p; p ^= p & -p) res += data[p];
    return res;
  }
 public:
  inline void clear() {
    memset(data, 0, sizeof data);
  }
  void add(int p, int v) {
    for (++p; p < N; p += p & -p) data[p] += v;
  }
  inline int query(int l, int r) {
    return query(r - 1) - query(l - 1);
  }
} bit[2];

int main() {
  init();
  for (int i = 0; i < n; ++i) if (!flag[i]) bit[0].add(pos[i], 1);
  for (int i = 0; i < n; ++i) {
    int x = b[i].second, y = c[x], z = flag[x];
    for (auto it : u[y]) {
      int k, id;
      std::tie(k, id) = it;
      int p = std::lower_bound(a, a + n, std::make_pair(k, r[x])) - a;
      ans[id] += bit[0].query(l[k], p) + bit[1].query(p, l[k + 1]);
    }
    if (z) bit[1].add(pos[x], 1); else bit[0].add(pos[x], -1);
  }
  bit[0].clear(), bit[1].clear();
  for (int i = 0; i < n; ++i) bit[1].add(pos[i], 1);
  for (int i = 0; i < n; ++i) {
    int x = b[i].second, y = c[x], z = flag[x];
    for (auto it : v[y]) {
      int k, id;
      std::tie(k, id) = it;
      int p = std::lower_bound(a, a + n, std::make_pair(k, r[x])) - a;
      ans[id] += z ? bit[1].query(l[k], p) : bit[0].query(p, l[k + 1]);
    }
    bit[0].add(pos[x], 1);
    bit[1].add(pos[x], -1);
  }
  for (int i = 0; i < q.size(); ++i) printf("%d\n", ans[i]);
  return 0;
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:123:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < q.size(); ++i) printf("%d\n", ans[i]);
                     ^
dragon2.cpp: In function 'void init()':
dragon2.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
                        ^
dragon2.cpp:54:83: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; ++i) scanf("%lld%lld%d", &p[i].x, &p[i].y, &c[i]), --c[i];
                                                                                   ^
dragon2.cpp:55:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &st.x, &st.y, &ed.x, &ed.y);
                                                        ^
dragon2.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
                  ^
dragon2.cpp:67:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
                          ^

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40