#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 30303
#define MAXS 20
#define INF 1000000100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
pii point[MAX];
vector<int> ps[MAX];
pii pos[MAX];
int op[2][MAX];
int ord[MAX];
vector<tuple<int, int, int>> qv[MAX];
vector<tuple<int, int, int>> tr[MAX * 2]; //tribe range, x, y, mul
int rev[2][MAX];
ll ans[MAX];
int chk[MAX];
inline ll ccw(pii p1, pii p2, pii p3) {
return (1ll * p1.first * p2.second + 1ll * p2.first * p3.second + 1ll * p3.first * p1.second) - (1ll * p2.first * p1.second + 1ll * p3.first * p2.second + 1ll * p1.first * p3.second);
}
int N, M;
inline void add(int i, pii rx, pii ry) {
if (rx == pii(0, 0)) return;
if (ry == pii(0, 0)) return;
if (rx.second == 0) rx.second = N;
if (ry.second == 0) ry.second = N;
if (rx.first == 0) rx.first = 1;
if (ry.first == 0) ry.first = 1;
if (rx.first > rx.second) {
add(i, pii(rx.first, N), ry);
add(i, pii(1, rx.second), ry);
return;
}
if (ry.first > ry.second) {
add(i, rx, pii(ry.first, N));
add(i, rx, pii(1, ry.second));
return;
}
tr[i].emplace_back(rx.second, ry.second, 1);
if (rx.first > 1) tr[i].emplace_back(rx.first - 1, ry.second, -1);
if (ry.first > 1) tr[i].emplace_back(rx.second, ry.first - 1, -1);
if (rx.first > 1 && ry.first > 1) tr[i].emplace_back(rx.first - 1, ry.first - 1, 1);
}
vector<int> tree;
vector<int> updv;
inline void upd(int i, int x) {
updv.push_back(i); while (i <= N) { tree[i] += x, i += i & -i; }
}
inline int get(int i) { int ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
inline void clear() {
for (auto v : updv) {
while (v <= N && tree[v]) {
tree[v] = 0;
v += v & -v;
}
}
updv.clear();
}
inline int nxv(int x) { return x % N + 1; }
inline int pvv(int x) { return (x + N - 2) % N + 1; }
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M;
int i, t;
for (i = 1; i <= N; i++) {
cin >> point[i].first >> point[i].second >> t;
ps[t].push_back(i);
}
point[++N] = pii(2 * INF, INF + 1);
point[++N] = pii(2 * INF, -INF + 1);
point[++N] = pii(-2 * INF, INF);
point[++N] = pii(-2 * INF, -INF);
pii X[2];
cin >> X[0].first >> X[0].second;
cin >> X[1].first >> X[1].second;
for (auto c : { 0, 1 }) {
vector<int> v1, v2;
point[0] = X[c ^ 1];
for (i = 0; i <= N; i++) ((point[i].second > X[c].second) ? v1 : v2).push_back(i);
sort(v1.begin(), v1.end(), [&](int i, int j) {
return ccw(X[c], point[i], point[j]) > 0;
});
sort(v2.begin(), v2.end(), [&](int i, int j) {
return ccw(X[c], point[i], point[j]) > 0;
});
vector<int> v = v1;
for (auto x : v2) v.push_back(x);
int ind;
for (i = 0; i < v.size(); i++) if (!v[i]) break;
ind = i;
vector<int> nv;
for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
for (i = 0; i < ind; i++) nv.push_back(v[i]);
swap(nv, v);
for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
int j = 1;
for (i = 1; i < v.size(); i++) {
while (ccw(point[v[i]], X[c], point[v[j]]) <= 0) {
j = (j + 1) % (N + 1);
if (i == j) break;
}
op[c][i] = j;
if (j < i && j) op[c][i] = (op[c][i] + N) % (N + 1), rev[c][v[i]] = 1;
if (i == j) j = (j + 1) % (N + 1);
}
}
for (i = 1; i <= M; i++) {
for (auto p : ps[i]) {
pii rx = pii(op[0][pos[p].first], pos[p].first);
pii ry = pii(op[1][pos[p].second], pos[p].second);
if (rev[0][p]) swap(rx.first, rx.second);
if (rev[1][p]) swap(ry.first, ry.second);
add(i, rx, ry);
rx = pii(op[0][pos[p].first], 0);
ry = pii(op[1][pos[p].second], 0);
if (rev[0][p]) swap(rx.first, rx.second);
if (rev[1][p]) swap(ry.first, ry.second);
add(i + M, rx, ry);
if (rev[0][p]) rx = pii(nxv(op[0][pos[p].first]), pos[p].first);
else rx = pii(pos[p].first, pvv(op[0][pos[p].first]));
if (rev[1][p]) ry = pii(nxv(op[1][pos[p].second]), pos[p].second);
else ry = pii(pos[p].second, pvv(op[1][pos[p].second]));
add(i + M, rx, ry);
}
}
for (i = 1; i <= M; i++) ord[i] = i;
sort(ord + 1, ord + N + 1, [&](int i, int j) {return ps[i].size() > ps[j].size(); });
int a, b;
int Q;
cin >> Q;
for (i = 1; i <= Q; i++) {
cin >> a >> b;
if (ord[a] < ord[b]) qv[a].emplace_back(b, 1, i);
else qv[b].emplace_back(a, 0, i);
}
tree.resize(N + 1);
for (i = 1; i <= M; i++) {
int v = ord[i];
vector<pair<tuple<int, int, int>, int>> rv;
for (auto& [p, m, q] : qv[v]) {
m *= M;
for (auto& t : tr[p + m]) rv.emplace_back(t, q);
}
sort(rv.begin(), rv.end());
clear();
int ptr = 0;
sort(ps[v].begin(), ps[v].end(), [&](int i, int j) {return pos[i].first < pos[j].first; });
for (auto& [t, q] : rv) {
auto& [x, y, mul] = t;
while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
ans[q] += mul * get(y);
}
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (i = 0; i < v.size(); i++) if (!v[i]) break;
| ~~^~~~~~~~~~
dragon2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (i = ind; i < v.size(); i++) nv.push_back(v[i]);
| ~~^~~~~~~~~~
dragon2.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (i = 1; i < v.size(); i++) (c ? pos[v[i]].second : pos[v[i]].first) = i;
| ~~^~~~~~~~~~
dragon2.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
dragon2.cpp:160:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | while (ptr < ps[v].size() && pos[ps[v][ptr]].first <= x) upd(pos[ps[v][ptr++]].second, 1);
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
116 ms |
5092 KB |
Output is correct |
| 4 |
Runtime error |
29 ms |
20300 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
14200 KB |
Output is correct |
| 2 |
Correct |
148 ms |
18200 KB |
Output is correct |
| 3 |
Correct |
46 ms |
11080 KB |
Output is correct |
| 4 |
Correct |
30 ms |
12364 KB |
Output is correct |
| 5 |
Correct |
36 ms |
13728 KB |
Output is correct |
| 6 |
Correct |
41 ms |
16788 KB |
Output is correct |
| 7 |
Correct |
40 ms |
16668 KB |
Output is correct |
| 8 |
Correct |
40 ms |
14132 KB |
Output is correct |
| 9 |
Correct |
38 ms |
17288 KB |
Output is correct |
| 10 |
Correct |
45 ms |
16756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4204 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4820 KB |
Output is correct |
| 3 |
Correct |
116 ms |
5092 KB |
Output is correct |
| 4 |
Runtime error |
29 ms |
20300 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
