// by szh
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DD;
#define int LL
#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}
const int maxn = 1e5 + 10;
const DD EPS = 1e-9;
struct dragon{
int t;
int x, y;
int id;
} da[maxn];
int xa, xb, ya, yb;
vector <pii> q[maxn];
int _;
int quadb(int x, int y) {
if (x >= 0 and y > 0) return 3;
if (x > 0 and y <= 0) return 0;
if (x <= 0 and y < 0) return 1;
assert(x < 0 and y >= 0);
return 2;
}
int quada(int x, int y) {
return (quadb(x, y) + 2) % 4;
}
bool cmp1(dragon a, dragon b) {
a.x -= xa; a.y -= ya;
b.x -= xa; b.y -= ya;
if (quada(a.x, a.y) != quada(b.x, b.y)) return quada(a.x, a.y) < quada(b.x, b.y);
else return a.y * b.x > b.y * a.x;
}
bool cmp2(dragon a, dragon b) {
if (a.t != b.t) return a.t < b.t;
a.x -= xb; a.y -= yb;
b.x -= xb; b.y -= yb;
if (quadb(a.x, a.y) != quadb(b.x, b.y)) return quadb(a.x, a.y) < quadb(b.x, b.y);
else return a.y * b.x > b.y * a.x;
}
vector <int> tree[maxn];
vector <pii> db[maxn];
int n, m;
void update(int x, int pos, int val) {
//if (val == 1) debug(x), debug(pos);
while (pos < SZ(tree[x])) {
tree[x][pos] += val;
pos += lowbit(pos);
}
return;
}
int query(int x, int pos) {
int ret = 0;
while (pos) {
ret += tree[x][pos];
pos -= lowbit(pos);
}
return ret;
}
int ans[maxn];
signed main() {
std::ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
rep(i, 0, n) {
cin >> da[i].x >> da[i].y >> da[i].t;
}
cin >> xa >> ya >> xb >> yb;
if (xa > xb) swap(xa, xb), swap(ya, yb);
sort(da, da + n, cmp2);
int cur = 0;
while (cur < n) {
int tmp = cur;
while (cur < n and da[cur].t == da[tmp].t) cur++;
tree[da[tmp].t].pb(0);
db[da[tmp].t].pb({0, 0});
rep(i, tmp, cur) {
da[i].id = i - tmp + 1;
tree[da[i].t].pb(0);
db[da[i].t].pb({da[i].x, da[i].y});
}
}
sort(da, da + n, cmp1);
rep(i, 0, n) da[i + n] = da[i];
cin >> _;
rep(i, 0, _) {
int x, y;
cin >> x >> y;
q[x].pb({y, i});
}
cur = 0;
bool flag = false;
rep(i, 0, n) {
int x1 = da[i].x - xa, y1 = da[i].y - ya, q1 = quada(x1, y1);
//debug(x1), debug(y1);
int x2 = -x1, y2 = -y1, q2 = (q1 + 2) % 4;
if (y1 <= 0 and flag == false) {
rep(j, i, cur) update(da[j].t, da[j].id, -1);
rep(j, 0, i) update(da[j].t, da[j].id, 1);
cur = 0;
flag = true;
}
if (q1 > q2) swap(x1, x2), swap(y1, y2), swap(q1, q2);
if (flag == false) {
if (cur > i) update(da[i].t, da[i].id, -1);
else cur = i + 1;
while (cur < n) {
int xx = da[cur].x - xa, yy = da[cur].y - ya, qq = quada(xx, yy);
if (qq > q2 or qq < q1 or (qq == q1 and y1 * xx < yy * x1) or (qq == q2 and y2 * xx > yy * x2)) break;
//debug(xx), debug(yy);
update(da[cur].t, da[cur].id, 1);
cur++;
}
} else {
update(da[i].t, da[i].id, 1);
while (cur < i) {
int xx = da[cur].x - xa, yy = da[cur].y - ya, qq = quada(xx, yy);
if (qq > q2 or qq < q1 or (qq == q1 and y1 * xx < yy * x1) or (qq == q2 and y2 * xx > yy * x2)) {
//debug(xx), debug(yy);
update(da[cur].t, da[cur].id, -1);
cur++;
}
else break;
}
}
for (auto itt : q[da[i].t]) {
int it = itt.F;
int xx = da[i].x - xb, yy = da[i].y - yb;
int q = quadb(xx, yy);
if (q == 0 or q == 1) xx *= -1, yy *= -1, q = (q + 2) % 4;
int L, R;
int lo = 0, hi = SZ(db[it]);
//debug(q), debug(xx), debug(yy);
while (lo < hi) {
int mid = lo + hi + 1 >> 1;
//cout << lo << " " << hi << " " << mid << endl;
if (mid == 0) lo = mid;
else if (mid == SZ(db[it])) hi = mid - 1;
else {
int xxx = db[it][mid].F, yyy = db[it][mid].S;
xxx -= xb, yyy -= yb;
//if (mid == 2) debug(xxx), debug(yyy), debug(it);
int qqq = quadb(xxx, yyy);
if (qqq > q or (qqq == q and yyy * xx < yy * xxx)) hi = mid - 1;
else lo = mid;
}
}
R = lo;
lo = 0, hi = SZ(db[it]);
q += 2, q %= 4;
xx *= -1, yy *= -1;
while (lo < hi) {
int mid = lo + hi >> 1;
if (mid == 0) lo = mid + 1;
else if (mid == SZ(db[it])) hi = mid;
else {
int xxx = db[it][mid].F, yyy = db[it][mid].S;
xxx -= xb, yyy -= yb;
int qqq = quadb(xxx, yyy);
if (qqq < q or (qqq == q and yyy * xx > yy * xxx)) lo = mid + 1;
else hi = mid;
}
}
L = lo;
//debug(L), debug(R);
//cout << ans[itt.S] << " ";
if (L <= R) ans[itt.S] += query(it, R) - query(it, L - 1);
//debug(ans[itt.S]);
}
}
rep(i, 0, _) cout << ans[i] << "\n";
return 0;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:164:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
164 | int mid = lo + hi + 1 >> 1;
| ~~~~~~~~^~~
dragon2.cpp:182:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
182 | int mid = lo + hi >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
