#include <cstdio>
#include <cstring>
#include <tuple>
#include <vector>
#include <algorithm>
typedef long long i64;
const int N = 30000 + 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
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);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5668 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5668 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5824 KB |
Output is correct |
| 4 |
Runtime error |
96 ms |
8164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
5668 KB |
Output is correct |
| 2 |
Correct |
73 ms |
5668 KB |
Output is correct |
| 3 |
Correct |
43 ms |
5668 KB |
Output is correct |
| 4 |
Correct |
36 ms |
5668 KB |
Output is correct |
| 5 |
Correct |
36 ms |
5668 KB |
Output is correct |
| 6 |
Correct |
39 ms |
5668 KB |
Output is correct |
| 7 |
Correct |
29 ms |
5668 KB |
Output is correct |
| 8 |
Correct |
39 ms |
5668 KB |
Output is correct |
| 9 |
Correct |
23 ms |
5668 KB |
Output is correct |
| 10 |
Correct |
26 ms |
5668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5668 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5668 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5824 KB |
Output is correct |
| 4 |
Runtime error |
96 ms |
8164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
