#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 = 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) {
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;
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;
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(dragon[i].clr > 0)
txValue[id] = i;
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) {
memset(tAnswer, 0, sizeof(tAnswer));
memset(act, 0, sizeof(act));
BIT.clear();
for(int it = 0;it < 2;it++){
for(int i = 1;i <= n + n;i++) {
const Event& cur = dragon[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]);
}
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: rQuery[atk]) {
if(answer[v.Y] != -1)
continue;
answer[v.X] = tAnswer[v.X];
}
}
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();
for(int i = 1;i <= m;i++) {
if(rQuery[i].size() + Query[i].size() >= block || 1)
solveHeavy(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";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7628 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
7688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
9156 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
8992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7628 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
7688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
