#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int maxN = 3e4 + 12, maxQ = 1e5 + 12, block = 0;
typedef pair<ll, ll> Point;
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;
}
int sign(ll val) {
if(val < 0) return -1;
if(val == 0) return 0;
return 1;
}
ll cross(Point a, Point b, Point c) {
a.X -= c.X, a.Y -= c.Y;
b.X -= c.X, b.Y -= c.Y;
return a.X * b.Y - a.Y * b.X;
}
struct Fenwick {
int f[maxN], was[maxN], timer = 0;
void upd(int v, int val) {
for(;v < maxN;v |= v + 1) {
if(was[v] != timer)
was[v] = timer, f[v] = 0;
f[v] += val;
}
}
int get(int v) {
int res = 0;
for(;v >= 0;v = (v & (v + 1)) - 1) {
if(was[v] != timer)
was[v] = timer, f[v] = 0;
res += f[v];
}
return res;
}
int get(int l, int r) {
if(r >= maxN) r = maxN - 1;
return get(r) - get(l - 1);
}
} fw;
struct Event {
int i, id, pr;
Point pos;
} p[maxN], events[maxN];
pair<Point, Point> city;
int n, m, q, qCnt[maxN], eLen;
ll answer[maxQ], tAnswer[maxN];
vector< pair<int, int> > query1[maxN], query2[maxN];
vector< int > g[maxN];
void inputs() {
cin >> n >> m;
for(int i = 1, x, y, id;i <= n;i++) {
cin >> x >> y >> id;
p[i] = {id, id, 0, {x, y}};
}
cin >> city.X.X >> city.X.Y >> city.Y.X >> city.Y.Y >> q;
}
void prepare1() {
sort(p + 1, p + n + 1,
[](const Event &lhs, const Event &rhs){
if(half(lhs.pos, city.Y) != half(rhs.pos, city.Y))
return half(lhs.pos, city.Y) < half(rhs.pos, city.Y);
return cross(lhs.pos, rhs.pos, city.Y) < 0;
}
);
for(int i = 1;i <= n;i++) p[i].id = i;
for(int i = 1, cnt = 0, ptr = i;i <= n;i++) {
while(cnt <= n && sign(cross(p[i].pos, city.Y, p[ptr].pos)) * sign(cross(p[i].pos, city.Y, city.X)) != -1) {
cnt++;
ptr = (ptr == n ? 1: ptr + 1);
}
cnt--;
if(cnt) p[i].pr = (cnt == n ? n - 1: cnt);
if(cnt == n) cnt = 0;
}
for(int i = n, cnt = 0, ptr = n;i >= 1;i--){
while(cnt <= n && sign(cross(p[i].pos, city.Y, p[ptr].pos)) * sign(cross(p[i].pos, city.Y, city.X)) != -1) {
cnt++;
ptr = (ptr == 1 ? n: ptr - 1);
}
cnt--;
if(cnt && !p[i].pr) p[i].pr = (cnt == n ? -n + 1: -cnt);
if(cnt == n) cnt = 0;
}
}
void prepare2() {
for(int i = 1;i <= n;i++) {
// cerr << p[i].pos.X << " " << p[i].pos.Y << " " << p[i].pr << "\n";
}
sort(p + 1, p + n + 1,
[](const Event &lhs, const Event &rhs){
if(half(lhs.pos, city.X) != half(rhs.pos, city.X))
return half(lhs.pos, city.X) < half(rhs.pos, city.X);
return cross(lhs.pos, rhs.pos, city.X) < 0;
}
);
for(int i = 1;i <= n;i++){
g[p[i].i].push_back(i);
}
}
int was[maxN], timer;
void solve(int atk) {
timer++, fw.timer++;
for(int i = 1, cnt = 0, ptr = 1;i <= eLen;i++) {
while(cnt <= n && sign(cross(p[i].pos, city.X, p[ptr].pos)) * sign(cross(p[i].pos, city.X, city.Y)) != -1) {
cnt++;
if((atk > 0 && p[ptr].i != atk) || (p[ptr].i == -atk))
fw.upd(p[ptr].id, 1);
ptr = (ptr == eLen ? 1: ptr + 1);
}
cnt--;
//cerr << p[i].pos.X << " " << p[i].pos.Y << " " << cnt << "\n";
if((atk > 0 && p[i].i != atk) || (p[i].i == -atk))
fw.upd(p[i].id, -1);
else if(cnt){
if(p[i].pr > 0) {
tAnswer[p[i].i] += fw.get(p[i].id, p[i].id + p[i].pr);
if(p[i].id + p[i].pr > n)
tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr - n);
}
else if(p[i].pr < 0) {
tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr, p[i].id);
if(p[i].id + p[i].pr < 1)
tAnswer[p[i].i] += fw.get(n - (p[i].id + p[i].pr), n);
}
was[i] = timer;
}
if(cnt == n) fw.timer++, cnt = 0;
}
fw.timer++;
for(int i = eLen, cnt = 0, ptr = eLen;i >= 1;i--) {
while(cnt <= n && sign(cross(p[i].pos, city.X, p[ptr].pos)) * sign(cross(p[i].pos, city.X, city.Y)) != -1) {
cnt++;
if((atk > 0 && p[ptr].i != atk) || (p[ptr].i == -atk))
fw.upd(p[ptr].id, 1);
ptr = (ptr == 1 ? eLen: ptr - 1);
}
cnt--;
if((atk > 0 && p[i].i != atk) || (p[i].i == -atk))
fw.upd(p[i].id, -1);
else if(cnt && was[i] != timer){
if(p[i].pr > 0) {
tAnswer[p[i].i] += fw.get(p[i].id, p[i].id + p[i].pr);
if(p[i].id + p[i].pr > n)
tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr - n);
}
else if(p[i].pr < 0) {
tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr, p[i].id);
if(p[i].id + p[i].pr < 1)
tAnswer[p[i].i] += fw.get(n - (p[i].id + p[i].pr), n);
}
assert(was[i] != timer);
was[i] = timer;
}
if(cnt == n) fw.timer++, cnt = 0;
}
}
void prepare(int me) {
memset(tAnswer, 0, sizeof(tAnswer));
solve(me), solve(-me);
for(pair<int, int> v: query1[me]) {
if(answer[v.Y] == -1) {
answer[v.Y] = tAnswer[me];
}
}
for(pair<int, int> v: query2[me]) {
if(answer[v.Y] == -1) {
answer[v.Y] = tAnswer[v.X];
}
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
inputs();
prepare1();
prepare2();
for(int i = 1, u, v;i <= q;i++) {
cin >> u >> v;
query1[u].push_back(MP(v, i));
query2[v].push_back(MP(u, i));
answer[i] = -1;
}
for(int i = 1;i <= n;i++)
events[i] = p[i];
eLen = n;
for(int i = 1;i <= m;i++) {
if(query1[i].size() + query2[i].size() >= block) {
prepare(i);
}
}
for(int i = 1;i <= q;i++) {
cout << answer[i] << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
28 ms |
10432 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
4684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
