#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int maxN = 7e4 + 12;
const int maxQ = 1e5 + 12;
const int block = 300, 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) {
assert(v < maxN);
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];
for(pair<int, int> v: Query[atk]) {
if(answer[v.Y] != -1)
continue;
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";
// if(cur.clr == 9 && it == 1)
// cerr << BIT.get(tValue[cur.id]) << "\n";
}
else if(tDragon[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(pair<int, int> v: Query[atk]) {
if(answer[v.Y] != -1)
continue;
answer[v.Y] = tAnswer[v.X];
}
for(int i = 1;i <= len;i++) {
const Event& cur = dragon[tDragon[i]];
act[cur.id] = 0;
tAnswer[abs(cur.clr)] = 0;
}
}
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) {
//return; // DEGB
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;
}
// cerr << "was\n";
}
}
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]);
// if(it == 1 && cur.clr == 9)
// cerr << BIT.get(tValue[cur.id]) << "s\n";
// 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:237:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
237 | for(int i = 0;i < gDragon[v.X].size();i++)
| ~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 2 |
Correct |
14 ms |
7884 KB |
Output is correct |
| 3 |
Correct |
93 ms |
8068 KB |
Output is correct |
| 4 |
Correct |
165 ms |
10284 KB |
Output is correct |
| 5 |
Correct |
74 ms |
10900 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8012 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8084 KB |
Output is correct |
| 8 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 9 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 10 |
Correct |
7 ms |
7884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
9576 KB |
Output is correct |
| 2 |
Correct |
119 ms |
9540 KB |
Output is correct |
| 3 |
Correct |
61 ms |
9620 KB |
Output is correct |
| 4 |
Correct |
38 ms |
9488 KB |
Output is correct |
| 5 |
Correct |
42 ms |
9832 KB |
Output is correct |
| 6 |
Correct |
36 ms |
9620 KB |
Output is correct |
| 7 |
Correct |
32 ms |
9484 KB |
Output is correct |
| 8 |
Correct |
40 ms |
9388 KB |
Output is correct |
| 9 |
Correct |
36 ms |
9560 KB |
Output is correct |
| 10 |
Correct |
37 ms |
9484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 2 |
Correct |
14 ms |
7884 KB |
Output is correct |
| 3 |
Correct |
93 ms |
8068 KB |
Output is correct |
| 4 |
Correct |
165 ms |
10284 KB |
Output is correct |
| 5 |
Correct |
74 ms |
10900 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8012 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8084 KB |
Output is correct |
| 8 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 9 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 10 |
Correct |
7 ms |
7884 KB |
Output is correct |
| 11 |
Correct |
43 ms |
9576 KB |
Output is correct |
| 12 |
Correct |
119 ms |
9540 KB |
Output is correct |
| 13 |
Correct |
61 ms |
9620 KB |
Output is correct |
| 14 |
Correct |
38 ms |
9488 KB |
Output is correct |
| 15 |
Correct |
42 ms |
9832 KB |
Output is correct |
| 16 |
Correct |
36 ms |
9620 KB |
Output is correct |
| 17 |
Correct |
32 ms |
9484 KB |
Output is correct |
| 18 |
Correct |
40 ms |
9388 KB |
Output is correct |
| 19 |
Correct |
36 ms |
9560 KB |
Output is correct |
| 20 |
Correct |
37 ms |
9484 KB |
Output is correct |
| 21 |
Correct |
52 ms |
9668 KB |
Output is correct |
| 22 |
Correct |
121 ms |
9556 KB |
Output is correct |
| 23 |
Correct |
1123 ms |
9720 KB |
Output is correct |
| 24 |
Correct |
1964 ms |
12024 KB |
Output is correct |
| 25 |
Correct |
261 ms |
12352 KB |
Output is correct |
| 26 |
Correct |
153 ms |
13068 KB |
Output is correct |
| 27 |
Correct |
43 ms |
10956 KB |
Output is correct |
| 28 |
Correct |
47 ms |
11012 KB |
Output is correct |
| 29 |
Correct |
146 ms |
21692 KB |
Output is correct |
| 30 |
Correct |
1279 ms |
12696 KB |
Output is correct |
| 31 |
Correct |
126 ms |
12996 KB |
Output is correct |
| 32 |
Correct |
126 ms |
13760 KB |
Output is correct |
| 33 |
Correct |
2155 ms |
12840 KB |
Output is correct |
| 34 |
Correct |
135 ms |
12996 KB |
Output is correct |
| 35 |
Correct |
141 ms |
13800 KB |
Output is correct |
| 36 |
Correct |
135 ms |
12832 KB |
Output is correct |
| 37 |
Correct |
150 ms |
13068 KB |
Output is correct |
| 38 |
Correct |
526 ms |
21656 KB |
Output is correct |
| 39 |
Correct |
1733 ms |
16780 KB |
Output is correct |
| 40 |
Correct |
2195 ms |
12864 KB |
Output is correct |
| 41 |
Correct |
144 ms |
21572 KB |
Output is correct |
| 42 |
Correct |
181 ms |
21640 KB |
Output is correct |
| 43 |
Correct |
191 ms |
21572 KB |
Output is correct |
| 44 |
Execution timed out |
4091 ms |
10316 KB |
Time limit exceeded |
| 45 |
Halted |
0 ms |
0 KB |
- |
