#include <bits/stdc++.h>
using namespace std;
#define int long long
struct pt {
int x, y;
pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};
bool const operator == (pt a, pt b) {
return a.x == b.x && a.y == b.y;
}
pt sim(pt a, pt b) {
return pt(b.x + (b.x - a.x), b.y + (b.y - a.y));
}
int orient(pt a, pt b, pt c) {
long long val = (b.y - a.y) * 1LL * (c.x - b.x) - (b.x - a.x) * 1LL * (c.y - b.y);
return (val == 0 ? 0 : (val > 0 ? 1 : -1)); // 1 clock, -1 counterclock
}
struct angle {
pt a, b, c;
};
bool const operator == (angle p, angle q) {
return p.a == q.a && p.b == q.b && p.c == q.c;
}
bool const operator < (angle p, angle q) {
if (p == q) {
return false;
}
int ps = orient(p.a, p.b, p.c);
int qs = orient(q.a, q.b, q.c);
if (orient(p.a, q.a, p.b) == 0) {
while (true) {
}
}
if (ps == qs) {
return orient(p.a, q.a, p.b) == ps;
} else {
// ...
while (true) {
}
return false;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<pt> p(n);
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> c[i];
--c[i];
}
pt a, b;
cin >> a.x >> a.y >> b.x >> b.y;
vector<vector<vector<int>>> ids(m, vector<vector<int>>(2));
vector<int> cnt(m);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
assert(o != 0);
int sd = (o == 1 ? 0 : 1);
ids[c[i]][sd].push_back(i);
cnt[c[i]] += 1;
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (orient(p[i], p[j], a) == 0) {
assert(false);
}
}
}
vector<vector<angle>> all_a(2);
vector<vector<angle>> all_b(2);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
int sd = (o == 1 ? 0 : 1);
pt p_a = sim(p[i], a);
pt p_b = sim(p[i], b);
all_a[sd].push_back({p[i], a, b});
all_b[sd].push_back({p[i], b, a});
all_a[sd ^ 1].push_back({p_a, a, b});
all_b[sd ^ 1].push_back({p_b, b, a});
}
for (int sd = 0; sd < 2; sd++) {
sort(all_a[sd].begin(), all_a[sd].end());
sort(all_b[sd].begin(), all_b[sd].end());
}
vector<int> ia(n);
vector<int> ib(n);
vector<int> ja(n);
vector<int> jb(n);
for (int i = 0; i < n; i++) {
int o = orient(a, b, p[i]);
int sd = (o == 1 ? 0 : 1);
{
angle A;
A.a = p[i];
A.b = a;
A.c = b;
int low = 0, high = (int) all_a[sd].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_a[sd][mid] == A) {
ia[i] = mid;
break;
} else if (all_a[sd][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ia[i] = (int) (lower_bound(all_a[sd].begin(), all_a[sd].end(), A) - all_a[sd].begin());
assert(A == all_a[sd][ia[i]]);
}
{
angle A;
A.a = p[i];
A.b = b;
A.c = a;
int low = 0, high = (int) all_b[sd].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_b[sd][mid] == A) {
ib[i] = mid;
break;
} else if (all_b[sd][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ib[i] = (int) (lower_bound(all_b[sd].begin(), all_b[sd].end(), A) - all_b[sd].begin());
assert(A == all_b[sd][ib[i]]);
}
{
angle A;
A.a = sim(p[i], a);
A.b = a;
A.c = b;
int low = 0, high = all_a[sd ^ 1].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_a[sd ^ 1][mid] == A) {
ja[i] = mid;
break;
} else if (all_a[sd ^ 1][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//ja[i] = (int) (lower_bound(all_a[sd ^ 1].begin(), all_a[sd ^ 1].end(), A) - all_a[sd ^ 1].begin());
assert(A == all_a[sd ^ 1][ja[i]]);
}
{
angle A;
A.a = sim(p[i], b);
A.b = b;
A.c = a;
int low = 0, high = all_b[sd ^ 1].size() - 1;
while (low <= high) {
int mid = low + high >> 1;
if (all_b[sd ^ 1][mid] == A) {
jb[i] = mid;
break;
} else if (all_b[sd ^ 1][mid] < A) {
low = mid + 1;
} else {
high = mid - 1;
}
}
//jb[i] = (int) (lower_bound(all_b[sd ^ 1].begin(), all_b[sd ^ 1].end(), A) - all_b[sd ^ 1].begin());
assert(A == all_b[sd ^ 1][jb[i]]);
}
}
int q;
cin >> q;
vector<int> f(q), g(q);
for (int i = 0; i < q; i++) {
cin >> f[i] >> g[i];
--f[i]; --g[i];
}
vector<int> qt(q, -1);
map<pair<int, int>, int> mp;
for (int i = 0; i < q; i++) {
if (mp.count({f[i], g[i]})) {
//qt[i] = mp[{f[i], g[i]}];
} else {
//mp[{f[i], g[i]}] = i;
}
}
vector<int> res(q);
{
vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
return ia[i] < ia[j];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] <= cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[f[qq]][sd]) {
{
int low = 0, high = (int) ids[g[qq]][sd].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ia[i] >= ia[ids[g[qq]][sd][mid]]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[g[qq]][sd][pos].emplace_back(qq, ib[i]);
}
}
{
int low = 0, high = (int) ids[g[qq]][sd ^ 1].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ja[i] >= ia[ids[g[qq]][sd ^ 1][mid]]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[g[qq]][sd ^ 1][pos].emplace_back(qq, jb[i]);
}
}
}
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
res[p.first] += Query(p.second);
}
}
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], -1);
}
}
}
}
{
/* vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
return ia[i] > ia[j];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
{
int low = 0, high = (int) ids[f[qq]][sd].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ia[ids[f[qq]][sd][mid]] >= ia[i]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[f[qq]][sd][pos].emplace_back(qq, ib[i]);
}
}
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
assert(0 <= x);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
assert(x < n);
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
res[p.first] += Query(n - 1) - Query(p.second - 1);
}
}
for (int k = 0; k < sz; k++) {
Modify(ib[ids[i][j][k]], -1);
}
}
}
} */
for (int qq = 0; qq < q; qq++) {
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[f[qq]][sd]) {
for (int j : ids[g[qq]][sd]) {
if (ia[i] >= ia[j] && ib[i] >= ib[j]) {
res[qq] += 1;
}
}
}
}
}
}
}
{
vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
for (int i = 0; i < m; i++) {
qs[i][0].resize(cnt[i]);
qs[i][1].resize(cnt[i]);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
sort(ids[i][j].begin(), ids[i][j].end(), [&](int x, int y) {
return ja[x] > ja[y];
});
}
}
for (int qq = 0; qq < q; qq++) {
if (qt[qq] != -1) {
continue;
}
if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
continue;
}
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
int sz = (int) ids[f[qq]][sd ^ 1].size();
for (int j = 0; j + 1 < sz; j++) {
assert(ja[ids[f[qq]][sd ^ 1][j]] >= ja[ids[f[qq]][sd ^ 1][j + 1]]);
}
int pos = -1;
while (pos + 1 < (int) ids[f[qq]][sd ^ 1].size() && ja[ids[f[qq]][sd ^ 1][pos + 1]] >= ia[i]) {
pos += 1;
}
if (pos != -1) {
qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
}
/* {
int low = 0, high = (int) ids[f[qq]][sd ^ 1].size() - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (ja[ids[f[qq]][sd ^ 1][mid]] >= ia[i]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
}
} */
}
}
}
vector<int> fenw(n);
auto Modify = [&](int x, int v) {
assert(0 <= x);
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
};
auto Query = [&](int x) {
assert(x < n);
int v = 0;
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < 2; j++) {
int sz = (int) ids[i][j].size();
for (int k = 0; k < sz; k++) {
// Modify(jb[ids[i][j][k]], +1);
for (auto& p : qs[i][j][k]) {
for (int w = 0; w <= k; w++) {
if (jb[ids[i][j][w]] >= p.second) {
res[p.first] += 1;
}
}
// res[p.first] += Query(n - 1) - Query(p.second - 1);
}
}
for (int k = 0; k < sz; k++) {
// Modify(jb[ids[i][j][k]], -1);
}
}
}
}
/* for (int qq = 0; qq < q; qq++) {
if (cnt[f[qq]] > cnt[g[qq]]) {
for (int sd = 0; sd < 2; sd++) {
for (int i : ids[g[qq]][sd]) {
for (int j : ids[f[qq]][sd ^ 1]) {
if (ja[j] < ia[i]) {
break;
}
if (jb[j] >= ib[i]) {
res[qq] += 1;
}
}
}
}
}
} */
}
for (int i = 0; i < q; i++) {
if (qt[i] != -1) {
res[i] = res[qt[i]];
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:114:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:134:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:154:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
154 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:174:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
174 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:231:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
231 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:246:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
246 | int mid = low + high >> 1;
| ~~~~^~~~~~
dragon2.cpp:432:12: warning: variable 'Modify' set but not used [-Wunused-but-set-variable]
432 | auto Modify = [&](int x, int v) {
| ^~~~~~
dragon2.cpp:439:12: warning: variable 'Query' set but not used [-Wunused-but-set-variable]
439 | auto Query = [&](int x) {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1436 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
1528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1418 ms |
9992 KB |
Output is correct |
| 2 |
Execution timed out |
4051 ms |
13172 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1436 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
1528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
