이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template <class T>
pair<T, T> _minmax(const T& a, const T& b) {
if (a < b)
return make_pair(a, b);
else
return make_pair(b, a);
}
typedef __int128 i128;
const int N = 30000, Q = 100000;
const i128 PI = (i128)1e36 * acosl(-1);
i128 acos2_128(int x, int y) { return (i128)1e36 * atan2l(y, x); }
i128 opposite(const i128& x) { return x < 0 ? x + PI : x - PI; }
struct point {
int x, y;
i128 ang_a, ang_b;
point() {}
point(int x, int y) : x(x), y(y) {}
i128 angle(const point& p) const { return acos2_128(p.x - x, p.y - y); }
} A, B;
int ans[Q];
namespace pst {
const int M = N * 15 * 2;
int sum[M], ll[M], rr[M], _;
void clear() { _ = 0; }
int node(int k = 0) {
++_;
sum[_] = sum[k];
ll[_] = ll[k], rr[_] = rr[k];
return _;
}
int build(int l, int r) {
int v = node(), m;
if (l < r) {
m = (l + r) / 2;
ll[v] = build(l, m);
rr[v] = build(m + 1, r);
}
return v;
}
int update(int v, int l, int r, int i, int x) {
int v_ = node(v), m;
sum[v_] += x;
if (l < r) {
m = (l + r) / 2;
if (i <= m)
ll[v_] = update(ll[v_], l, m, i, x);
else
rr[v_] = update(rr[v_], m + 1, r, i, x);
}
return v_;
}
int query(int v, int l, int r, int ql, int qr) {
int m;
if (qr < l || ql > r) return 0;
if (ql <= l && qr >= r) return sum[v];
m = (l + r) / 2;
return query(ll[v], l, m, ql, qr) + query(rr[v], m + 1, r, ql, qr);
}
} // namespace pst
struct group {
vector<int> vv;
vector<i128> xx, yy;
vector<point> pp;
int n;
int size() { return n; }
void add(const point& p) { pp.push_back(p), n++; }
void add_query(const i128& lx, const i128& rx, const i128& ly, const i128& ry,
int h) {
short l = lower_bound(yy.begin(), yy.end(), ly) - yy.begin();
short r = upper_bound(yy.begin(), yy.end(), ry) - yy.begin() - 1;
short l_ = lower_bound(xx.begin(), xx.end(), lx - 1) - xx.begin();
short r_ = upper_bound(xx.begin(), xx.end(), rx) - xx.begin() - 1;
ans[h] += pst::query(vv[r_ + 1], 0, yy.size() - 1, l, r) -
pst::query(vv[l_], 0, yy.size() - 1, l, r);
}
void add1(const point& q, int h) {
auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
bool side_a = l_a <= B.ang_a && B.ang_a <= r_a;
auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
bool side_b = l_b <= A.ang_b && A.ang_b <= r_b;
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
}
void add2(const point& q, int h) {
auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
bool side_a = !(l_a <= B.ang_a && B.ang_a <= r_a);
auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
bool side_b = !(l_b <= A.ang_b && A.ang_b <= r_b);
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
tie(l_a, r_a) = _minmax(opposite(q.ang_a), B.ang_a);
side_a = !(l_a <= q.ang_a && q.ang_a <= r_a);
tie(l_b, r_b) = _minmax(opposite(q.ang_b), A.ang_b);
side_b = !(l_b <= q.ang_b && q.ang_b <= r_b);
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
}
void build() {
for (const point& p : pp) {
xx.push_back(p.ang_a);
yy.push_back(p.ang_b);
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
sort(pp.begin(), pp.end(),
[&](const point& p, const point& q) { return p.ang_a < q.ang_a; });
pst::clear();
vv.push_back(pst::build(0, yy.size() - 1));
for (const point& p : pp) {
int i = lower_bound(yy.begin(), yy.end(), p.ang_b) - yy.begin();
vv.push_back(pst::update(vv.back(), 0, yy.size() - 1, i, +1));
}
}
void clear() {
xx.clear();
yy.clear();
}
} gr[N];
int main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
static vector<tuple<int, int, bool>> todo[N];
vector<pair<point, int>> pp;
int n, m, q;
cin >> n >> m;
pp.resize(n);
for (auto& [p, c] : pp) cin >> p.x >> p.y >> c, c--;
cin >> A.x >> A.y >> B.x >> B.y;
A.ang_a = A.angle(A);
A.ang_b = B.angle(A);
B.ang_a = A.angle(B);
B.ang_b = B.angle(B);
for (auto& [p, c] : pp) {
p.ang_a = A.angle(p);
p.ang_b = B.angle(p);
gr[c].add(p);
}
pp.clear();
cin >> q;
for (int h = 0; h < q; h++) {
int c1, c2;
cin >> c1 >> c2, c1--, c2--;
if (gr[c1].size() < gr[c2].size())
todo[c2].push_back({c1, h, 0});
else
todo[c1].push_back({c2, h, 1});
}
for (int c = 0; c < m; c++) {
gr[c].build();
for (auto [c_, h, t] : todo[c])
for (const point& p : gr[c_].pp)
if (t == 0)
gr[c].add1(p, h);
else
gr[c].add2(p, h);
gr[c].clear();
todo[c].clear();
}
for (int h = 0; h < q; h++) cout << ans[h] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |