#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define N 200001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
struct Pt {
ll x, y;
Pt (int x, int y) : x (x), y (y) {}
Pt () : x (0), y (0) {}
ll cross (const Pt& b) const { return x * b.y - b.x * y; }
bool operator < (const Pt& b) const { return cross (b) < 0; }
Pt operator - (const Pt& b) const { return Pt (x - b.x, y - b.y); }
Pt operator - () const { return Pt (-x, -y); }
} s, e;
bool OO = true;
vector <int> vs[N];
Pt p[N], pe[N], ps[N];
vector < pair <Pt, int> > ords, orde;
unordered_map <int, ll> qu[N];
ll big[N], sz[N];
int n, m, q, bl = 400, refl[N], g[N];
struct BIT {
int n;
vector <int> t;
BIT () {}
BIT (int n) : n (n), t (vector <int> (n + 1)) {}
void update (int x, int d) {
for (; x <= n; x = (x | (x + 1)))
t[x] += d;
}
int get (int r) {
int sum = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
sum += t[r];
return sum;
}
int get (int l, int r) { return get (r) - get (l - 1); }
} t1 (N), t2 (N);
int find_e (Pt x) {
return lower_bound (orde.begin(), orde.end(), make_pair (x,-1)) - orde.begin ();
}
void attack_to (int to) {
t1 = BIT (n);
t2 = BIT (n);
for (int i = 0; i < n; i++) {
if (g[i] == to && !refl[i]) t2.update (find_e (pe[i]), 1);
}
for (int i = 0; i < n; i++) {
int x = ords[i].second, tribe = g[x];
int ind = find_e (pe[i]);
if (tribe == to) {
if (!refl[i]) t2.update (ind, -1);
else t1.update (ind, 1);
continue;
}
if (qu[tribe].find (x) == qu[tribe].end ()) continue;
qu[tribe][x] += t2.get (0, ind - 1) + t1.get (ind, n - 1);
}
for (int i = 0; i < n; i++) {
cur = find_e (pe[i]);
if (t1.get (cur, cur)) t1.update (cur, -1);
if (t2.get (cur, cur)) t2.update (cur, -1);
}
}
void attack_from (int from) {
t1 = BIT (n);
t2 = BIT (n);
for (int i = 0; i < n; i++) {
if (g[i] == from) t2.update (find_e (pe[i]), 1);
}
for (int i = 0; i < n; i++) {
int x = ords[i].second, tribe = g[x];
int ind = find_e (pe[i]);
if (tribe == from) {
t1.update (ind, 1);
t2.update (ind, -1);
continue;
}
if (qu[tribe].find (x) == qu[tribe].end ()) continue;
if (refl[x]) {
qu[x][tribe] += t2.get (0, ind - 1);
} else {
qu[x][tribe] += t1.get (ind, n - 1);
}
}
for (int i = 0; i < n; i++) {
cur = find_e (pe[i]);
if (t1.get (cur, cur)) t1.update (cur, -1);
if (t2.get (cur, cur)) t2.update (cur, -1);
}
}
int attack_small (int from, int to) {
ll sum = 0;
if (OO) cout << "Vectors to:" << endl;
for (int i : vs[to]) {
int x = ords[i].second;
if (!refl[x]) {
t2.update (find_e (pe[x]), 1);
if (OO) cout << "t2 Adding " << pe[i].x << ' ' << pe[i].y << ' ' << find_e (pe[i]) << endl;
}
}
int j = 0;
if (OO) cout << "Vectors from:" << endl;
for (int i : vs[from]) {
int x = ords[i].second;
if (OO) cout << pe[x].x << ' ' << pe[x].y << ' ' << i << endl;
int ind = find_e (pe[x]);
while (j < vs[to].size () && vs[to][j] < i) {
int cur = ords[vs[to][j]].second;
if (!refl[cur]) {
t2.update (find_e (pe[cur]), -1);
if (OO) cout << "t2 Deleting " << pe[cur].x << ' ' << pe[cur].y << ' ' << find_e (pe[cur]) << endl;
}
else {
t1.update (find_e (pe[cur]), 1);
if (OO) cout << "t1 Adding " << pe[cur].x << ' ' << pe[cur].y << ' ' << find_e (pe[cur]) << endl;
}
j++;
}
if (OO) cout << "Checking by " << pe[x].x << ' ' << pe[x].y << ' ' << find_e (pe[x]) << endl;
sum += t1.get (ind, n - 1) + t2.get (0, ind - 1);
}
for (int i : vs[to]) {
int x = ords[i].second, cur = find_e (pe[x]);
if (t1.get (cur, cur)) t1.update (cur, -1);
if (t2.get (cur, cur)) t2.update (cur, -1);
}
if (OO) {
for (int i = 0; i < n; i++)
cout << t2.get (i, i);
cout << endl;
}
return sum;
}
int main () {
OO = false;
cin >> n >> m;
for (int i = 0; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
g[i] = c - 1;
p[i] = Pt (a, b);
}
int x, y;
cin >> x >> y;
s = Pt (x, y);
cin >> x >> y;
e = Pt (x, y);
for (int i = 0; i < n; i++) {
ps[i] = p[i] - s;
pe[i] = p[i] - e;
if (ps[i].cross (e - s) > 0) {
refl[i] = 1;
ps[i] = -ps[i], pe[i] = -pe[i];
}
orde.push_back ({pe[i], i});
ords.push_back ({ps[i], i});
}
sort (ords.begin(), ords.end());
sort (orde.begin(), orde.end());
for (int i = 0; i < n; i++) {
vs[g[ords[i].second]].push_back (i);
}
cin >> q;
vector < pair <int, int> > e;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
a--, b--;
e.emplace_back (a, b);
qu[a][b] = i;
}
for (int i = 0; i < m; i++) {
if (sz[i] > bl) {
big[i] = 1;
attack_from (i);
attack_to (i);
}
}
for (auto [a, b] : e) {
if (!big[a] && !big[b]) cout << attack_small (a, b) << endl;
else if (big[a] && big[b]) cout << qu[a][b] / 2 << endl;
else cout << qu[a][b] << endl;
}
}
Compilation message
dragon2.cpp: In function 'void attack_to(int)':
dragon2.cpp:93:3: error: 'cur' was not declared in this scope
93 | cur = find_e (pe[i]);
| ^~~
dragon2.cpp: In function 'void attack_from(int)':
dragon2.cpp:127:3: error: 'cur' was not declared in this scope
127 | cur = find_e (pe[i]);
| ^~~
dragon2.cpp: In function 'int attack_small(int, int)':
dragon2.cpp:153:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | while (j < vs[to].size () && vs[to][j] < i) {
| ~~^~~~~~~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:243:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
243 | for (auto [a, b] : e) {
| ^
