#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int maxN = 6e4 + 12;
const int maxQ = 1e5 + 12;
const int block = 330, INF = 1e9 + 7;
typedef pair<ll, ll> Point;
Point origin;
struct Fenwick {
int f[maxN], was[maxN], timer = 0;
void clear() {
timer++;
}
void upd(int v, int val) {
for(;v < maxN;v |= v + 1) {
if(was[v] != timer)
f[v] = 0, was[v] = timer;
f[v] += val;
}
}
int get(int v) {
int res = 0;
for(;v >= 0;v = (v & (v + 1)) - 1) {
if(was[v] != timer)
f[v] = 0, was[v] = timer;
res += f[v];
}
return res;
}
int get(int l, int r) {
if(l > r) {
return get(maxN - 1) - get(l - 1) + get(r);
}
else {
return get(r) - get(l - 1);
}
}
} BIT;
struct node {
int s = 0;
node *l = nullptr, *r = nullptr;
};
int tree_ptr;
node* tree[maxN];
node* upd(node* v, int tl, int tr, int pos, int val) {
if(tl == tr)
return new node {(v ? v->s: 0) + val, nullptr, nullptr};
int tm = (tl + tr) / 2;
if(pos <= tm) {
return new node {(v ? v->s: 0) + val, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v};
}
else {
return new node {(v ? v->s: 0) + val, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val)};
}
}
int get(node* v, int tl, int tr, int l, int r){
if(!v || tl > r || l > tr)
return 0;
if(tl >= l && tr <= r)
return v->s;
int tm = (tl + tr) / 2;
return get(v->l, tl, tm, l, r) + get(v->r, tm + 1, tr, l, r);
}
int sign(ll value) {
if(value > 0) return 1;
if(value < 0) return -1;
return 0;
}
int half(Point a, Point b) {
if(a.X != b.X)
return a.X < b.X ? 1: -1;
return a.Y < b.Y ? 1: -1;
}
ll cross(Point a, Point b, Point c) {
a.X -= c.X, b.X -= c.X;
a.Y -= c.Y, b.Y -= c.Y;
return a.X * b.Y - a.Y * b.X;
}
struct Event {
int clr, id;
Point pos;
};
bool operator < (const Event &lhs, const Event &rhs) {
int lhs_h = half(lhs.pos, origin);
int rhs_h = half(rhs.pos, origin);
if(lhs_h != rhs_h)
return lhs_h < rhs_h;
return cross(lhs.pos, rhs.pos, origin) < 0;
}
int n, m, q, tValue[maxN], txValue[maxN];
ll answer[maxQ];
pair< Point, Point > city;
pair< int, int > border[maxN], xBorder[maxN];
vector< pair<int, int> > rQuery[maxN], Query[maxN];
vector< int > gDragon[maxN];
Event dragon[maxN];
// border - y, area - x
void inputs() {
memset(answer, -1, sizeof(answer));
cin >> n >> m;
for(int i = 1, x, y, clr;i <= n;i++){
cin >> x >> y >> clr;
// x += INF, y += INF;
dragon[i] = {clr, i, {x, y}};
dragon[i + n] = {-clr, i, {-x, -y}};
}
cin >> city.X.X >> city.X.Y >> city.Y.X >> city.Y.Y;
cin >> q;
for(int i = 1, u, v;i <= q;i++){
cin >> u >> v;
Query[u].push_back({v, i});
rQuery[v].push_back({u, i});
}
}
void normalize() {
for(int i = 1;i <= n + n;i++) {
if(dragon[i].clr > 0) {
dragon[i].pos.X -= origin.X;
dragon[i].pos.Y -= origin.Y;
}
else {
dragon[i].pos.X += origin.X;
dragon[i].pos.Y += origin.Y;
}
}
city.X.X -= origin.X, city.Y.X -= origin.X;
city.X.Y -= origin.Y, city.Y.Y -= origin.Y;
}
void d_normalize() {
for(int i = 1;i <= n + n;i++) {
if(dragon[i].clr > 0) {
dragon[i].pos.X += origin.X;
dragon[i].pos.Y += origin.Y;
}
else {
dragon[i].pos.X -= origin.X;
dragon[i].pos.Y -= origin.Y;
}
}
city.X.X += origin.X, city.Y.X += origin.X;
city.X.Y += origin.Y, city.Y.Y += origin.Y;
}
void prepare() {
origin = city.Y;
auto mem = origin;
normalize(), origin = MP(0, 0);
sort(dragon + 1, dragon + n + n + 1);
for(int i = 1, id;i <= n + n;i++){
id = dragon[i].id;
if(dragon[i].clr > 0)
tValue[id] = i, txValue[i] = id;
if(border[id].X == 0)
border[id].X = i;
else
border[id].Y = i;
}
for(int i = 1;i <= n;i++) {
Event cur = dragon[border[i].X];
Event rev = dragon[border[i].Y];
if(cross(cur.pos, rev.pos, city.X) < 0)
swap(border[i].X, border[i].Y);
//cerr << i << ": " << border[i].X << " " << border[i].Y << "\n";
}
origin = mem;
d_normalize();
origin = city.X, mem = origin;
normalize(), origin = MP(0, 0);
sort(dragon + 1, dragon + n + n + 1);
for(int i = 1, id;i <= n + n;i++) {
gDragon[abs(dragon[i].clr)].push_back(i);
id = dragon[i].id;
if(xBorder[id].X == 0)
xBorder[id].X = i;
else
xBorder[id].Y = i;
} /*
for(int i = 1;i <= n + n;i++) {
int val = 0;
if(dragon[i].clr < 0) continue;
cerr << dragon[i].id << " " << i << "\n";
} */
for(int i = 1;i <= n;i++) {
const Event& cur = dragon[xBorder[i].X];
const Event& rev = dragon[xBorder[i].Y];
if(cross(cur.pos, rev.pos, city.Y) < 0)
swap(xBorder[i].X, xBorder[i].Y);
//cerr << i << ": " << xBorder[i].X << " " << xBorder[i].Y << "\n";
}
}
void add_interval(pair<int, int> v, int val) {
if(v.X <= v.Y) {
BIT.upd(v.X, val);
BIT.upd(v.Y + 1, -val);
}
else {
BIT.upd(v.X, val);
BIT.upd(1, val);
BIT.upd(v.Y + 1, -val);
}
}
ll tAnswer[maxN];
int tDragon[maxN], act[maxN];
void solveHeavy(int atk) {
BIT.clear();
int len = gDragon[atk].size();
for(int i = 1;i <= len;i++)
tDragon[i] = gDragon[atk][i - 1];
tAnswer[atk] = 0;
for(pair<int, int> v: Query[atk]) {
if(answer[v.Y] != -1)
continue;
tAnswer[v.X] = 0;
for(int i = 0;i < gDragon[v.X].size();i++)
tDragon[++len] = gDragon[v.X][i];
}
sort(tDragon + 1, tDragon + len + 1);
for(int it = 0;it < 2;it++){
for(int i = 1;i <= len;i++) {
const Event& cur = dragon[tDragon[i]];
if(cur.clr < 0 && cur.clr != -atk)
continue;
if(abs(cur.clr) != atk) {
if(it == 1)
tAnswer[cur.clr] += BIT.get(tValue[cur.id]);
//cerr << tAnswer[cur.clr] << "\n";
}
else if(i == xBorder[cur.id].X) {
if(!act[cur.id]) {
act[cur.id] = 1;
add_interval(border[cur.id], 1);
}
}
else {
if(act[cur.id]) {
act[cur.id] = 0;
add_interval(border[cur.id], -1);
}
}
}
}
for(int i = 1;i <= len;i++) {
act[dragon[tDragon[i]].id] = 0;
}
for(pair<int, int> v: Query[atk]) {
if(answer[v.Y] != -1)
continue;
answer[v.Y] = tAnswer[v.X];
}
}
int get(int x, int l, int r){
if(l <= r)
return get(tree[x], 1, n + n, l, r);
//cerr << get(tree[x], 1, n + n, l, n + n) << " " << get(tree[x], 1, n + n, 1, r) << " = ";
return get(tree[x], 1, n + n, l, n + n) + get(tree[x], 1, n + n, 1, r);
}
int get(int xl, int xr, int l, int r) {
// cerr << xl << " " << xr << " " << l << " " << r << "\n";
if(xl <= xr)
return get(xr, l, r) - get(xl - 1, l, r);
//cerr << "1: " << get(n + n, l, r) << "\n2: " << get(xr - 1, l, r) << "\n3: " << get(xl, l, r) << "\n";
return get(n + n, l, r) - get(xl - 1, l, r) + get(xr, l, r);
}
void solveHeavyR(int atk) {
for(int i = 1;i <= n + n;i++) {
tree[i] = tree[i - 1];
int id = dragon[i].id;
if(dragon[i].clr == atk) {
// cerr << i << " " << tValue[id] << "\n";
tree[i] = upd(tree[i], 1, n + n, tValue[id], 1);
}
}
for(pair<int, int> v: rQuery[atk]) {
if(answer[v.Y] != -1)
continue;
answer[v.Y] = 0;
for(int i: gDragon[v.X]) {
if(dragon[i].clr < 0) continue;
int id = dragon[i].id;
int add = get(xBorder[id].X, xBorder[id].Y, border[id].X, border[id].Y);
answer[v.Y] += add;
}
}
}
ll solveLight(int atk, int def) {
int lens = gDragon[atk].size() + gDragon[def].size();
ll res = 0;
merge(gDragon[atk].begin(), gDragon[atk].end(),
gDragon[def].begin(), gDragon[def].end(), tDragon + 1);
BIT.clear();
for(int it = 0;it < 2;it++){
for(int i = 1;i <= lens;i++) {
const Event& cur = dragon[tDragon[i]];
if(-cur.clr == def)
continue;
if(cur.clr == def) {
if(it == 1)
res += BIT.get(tValue[cur.id]);
// cerr << cur.id << " " << tValue[cur.id] << "gg\n";
}
else if(tDragon[i] == xBorder[cur.id].X) {
if(!act[cur.id]) {
act[cur.id] = 1;
// cerr << cur.id << " " << border[cur.id].X << " " << border[cur.id].Y << "was+\n";
add_interval(border[cur.id], 1);
}
}
else {
if(act[cur.id]) {
act[cur.id] = 0;
// cerr << cur.id << " " << border[cur.id].X << " " << border[cur.id].Y << "was-\n";
add_interval(border[cur.id], -1);
}
}
}
}
for(int i = 1;i <= lens;i++) {
const Event& cur = dragon[tDragon[i]];
act[cur.id] = 0;
}
return res;
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
inputs();
prepare();
vector<int> ord(m);
for(int i = 0;i < m;i++)
ord[i] = i + 1;
sort(ord.begin(), ord.end(), [](int lhs, int rhs){return gDragon[lhs].size() > gDragon[rhs].size();});
for(int i: ord) {
if(rQuery[i].size() >= block)
solveHeavy(i), solveHeavyR(i);
}
for(int i = 1;i <= m;i++) {
for(pair<int, int> v: Query[i]) {
if(answer[v.Y] != -1)
continue;
answer[v.Y] = solveLight(i, v.X);
}
}
for(int i = 1;i <= q;i++)
cout << answer[i] << "\n";
}
Compilation message
dragon2.cpp: In function 'void solveHeavy(int)':
dragon2.cpp:238:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
238 | for(int i = 0;i < gDragon[v.X].size();i++)
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6988 KB |
Output is correct |
| 2 |
Correct |
13 ms |
7020 KB |
Output is correct |
| 3 |
Correct |
86 ms |
7108 KB |
Output is correct |
| 4 |
Correct |
181 ms |
9412 KB |
Output is correct |
| 5 |
Correct |
73 ms |
9892 KB |
Output is correct |
| 6 |
Correct |
7 ms |
7128 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7148 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6996 KB |
Output is correct |
| 10 |
Correct |
6 ms |
6988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
8676 KB |
Output is correct |
| 2 |
Correct |
121 ms |
8568 KB |
Output is correct |
| 3 |
Correct |
63 ms |
8648 KB |
Output is correct |
| 4 |
Correct |
40 ms |
8548 KB |
Output is correct |
| 5 |
Correct |
40 ms |
8900 KB |
Output is correct |
| 6 |
Correct |
38 ms |
8672 KB |
Output is correct |
| 7 |
Correct |
33 ms |
8560 KB |
Output is correct |
| 8 |
Correct |
40 ms |
8456 KB |
Output is correct |
| 9 |
Correct |
36 ms |
8488 KB |
Output is correct |
| 10 |
Correct |
36 ms |
8552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6988 KB |
Output is correct |
| 2 |
Correct |
13 ms |
7020 KB |
Output is correct |
| 3 |
Correct |
86 ms |
7108 KB |
Output is correct |
| 4 |
Correct |
181 ms |
9412 KB |
Output is correct |
| 5 |
Correct |
73 ms |
9892 KB |
Output is correct |
| 6 |
Correct |
7 ms |
7128 KB |
Output is correct |
| 7 |
Correct |
8 ms |
7148 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6996 KB |
Output is correct |
| 10 |
Correct |
6 ms |
6988 KB |
Output is correct |
| 11 |
Correct |
45 ms |
8676 KB |
Output is correct |
| 12 |
Correct |
121 ms |
8568 KB |
Output is correct |
| 13 |
Correct |
63 ms |
8648 KB |
Output is correct |
| 14 |
Correct |
40 ms |
8548 KB |
Output is correct |
| 15 |
Correct |
40 ms |
8900 KB |
Output is correct |
| 16 |
Correct |
38 ms |
8672 KB |
Output is correct |
| 17 |
Correct |
33 ms |
8560 KB |
Output is correct |
| 18 |
Correct |
40 ms |
8456 KB |
Output is correct |
| 19 |
Correct |
36 ms |
8488 KB |
Output is correct |
| 20 |
Correct |
36 ms |
8552 KB |
Output is correct |
| 21 |
Correct |
41 ms |
8680 KB |
Output is correct |
| 22 |
Correct |
113 ms |
8584 KB |
Output is correct |
| 23 |
Correct |
1046 ms |
8740 KB |
Output is correct |
| 24 |
Correct |
1958 ms |
11056 KB |
Output is correct |
| 25 |
Correct |
278 ms |
11364 KB |
Output is correct |
| 26 |
Correct |
152 ms |
12068 KB |
Output is correct |
| 27 |
Correct |
46 ms |
9984 KB |
Output is correct |
| 28 |
Correct |
54 ms |
10088 KB |
Output is correct |
| 29 |
Incorrect |
142 ms |
20644 KB |
Output isn't correct |
| 30 |
Halted |
0 ms |
0 KB |
- |
