//#define debug
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef long double ld;
#define SZ(x) ((int)x.size())
const int SQ = 316;
const int N = (int)3e4+5;
struct point {
ll x, y;
int t, idx;
point(ll _x, ll _y, int _t, int _idx) : x(_x), y(_y), t(_t), idx(_idx) {}
point() { x = y = 0, t = idx = 0; }
inline bool operator<(const point &other) const;
} origin;
inline bool ccw(const point &a, const point &b, const point &c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}
struct TData {
int lo, hi, id;
TData(int _lo, int _hi, int _id) : lo(_lo), hi(_hi), id(_id) {}
TData() {}
inline bool operator<(const TData &other) const {
return hi < other.hi;
}
};
int n, m, q;
ll res[N], cnt[N];
vector<point> dragon, dragon2;
point human1, mid, human2;
vector<ii> b[N], c[N];
vector<TData> g[SQ+5];
vector<int> pos_t[N];
inline bool point::operator <(const point &other) const {
if (ccw(human2, *this, human1) && !ccw(human2, other, human1)) {
return true;
} else if (!ccw(human2, *this, human1) && ccw(human2, other, human1)) {
return false;
}
return ccw(origin, *this, other);
}
struct fenwick {
private:
vector<int> tree;
int _n;
public:
void init(int _sz) {
tree.resize(_sz + 1);
_n = _sz;
}
void update(int idx, int val) {
for (; idx <= _n; idx += idx & -idx)
tree[idx] += val;
}
int read(int idx) {
int ans = 0;
for (; idx; idx -= idx & -idx)
ans += tree[idx];
return ans;
}
void clear() {
if (!SZ(tree)) return;
tree.clear();
}
} tr[N];
void solve(ll mul, ll mul2) {
sort(dragon.begin(), dragon.end());
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i <= 316; ++i) g[i].clear();
for (int i = 0; i < n; ++i) {
point tmp = point(mul2 * dragon[i].x, mul2 * dragon[i].y, 0, 0);
int lo = upper_bound(dragon.begin(), dragon.end(), tmp) - dragon.begin();
int hi = upper_bound(dragon.begin(), dragon.end(), human1) - dragon.begin();
lo -= (mul2 == 1 && !ccw(human2, dragon[i], human1));
if (hi < lo) swap(lo, hi);
--hi;
if (lo <= hi) {
g[lo / SQ].push_back(TData(lo, hi, dragon[i].t));
}
}
for (int i = 0; i <= 316; ++i) {
sort(g[i].begin(), g[i].end());
}
for (int i = 0; i <= 316; ++i) {
if (!SZ(g[i])) continue;
memset(cnt, 0, sizeof(cnt));
int Lmax = -1;
for (const TData &v : g[i]) {
Lmax = max(Lmax, v.lo);
}
int curL = Lmax - 1;
for (const TData &v : g[i]) {
int L = v.lo, R = v.hi, t = v.id;
if (R - L + 1 <= SQ) {
for (int j = L; j <= R; ++j) {
++cnt[dragon[j].t];
}
} else {
while (curL < R) {
++curL;
++cnt[dragon[curL].t];
}
for (int j = L; j < Lmax; ++j) {
++cnt[dragon[j].t];
}
}
for (int j = 0; j < SZ(b[t]); ++j) {
res[b[t][j].second] += mul * cnt[b[t][j].first];
}
if (mul2 == -1) {
for (int j = 0; j < SZ(c[t]); ++j) {
res[c[t][j].second] += mul * cnt[c[t][j].first];
}
}
if (R - L + 1 <= SQ) {
for (int j = L; j <= R; ++j) {
--cnt[dragon[j].t];
}
} else {
for (int j = L; j < Lmax; ++j) {
--cnt[dragon[j].t];
}
}
}
}
}
int pos[N];
void solve2(vector<point> &a1, vector<point> &a2) {
memset(pos, 0, sizeof(pos));
for (int i = 1; i <= m; ++i) {
pos_t[i].clear();
tr[i].clear();
}
for (int i = 0; i < SZ(a2); ++i) {
pos[a2[i].idx] = i;
pos_t[a2[i].t].push_back(i);
}
for (int i = 1; i <= m; ++i) {
if (!SZ(pos_t[i])) continue;
tr[i].init(SZ(pos_t[i]));
}
for (const point &v : a1) {
int pvidx = pos[v.idx];
int idx = lower_bound(pos_t[v.t].begin(), pos_t[v.t].end(), pvidx) - pos_t[v.t].begin() + 1;
tr[v.t].update(idx, 1);
for (int j = 0; j < SZ(b[v.t]); ++j) {
int idx2 = upper_bound(pos_t[b[v.t][j].first].begin(), pos_t[b[v.t][j].first].end(), pvidx) - pos_t[b[v.t][j].first].begin();
int val = tr[b[v.t][j].first].read(idx2);
res[b[v.t][j].second] += (ll)(idx2 - val);
}
for (int j = 0; j < SZ(c[v.t]); ++j) {
int idx2 = upper_bound(pos_t[c[v.t][j].first].begin(), pos_t[c[v.t][j].first].end(), pvidx) - pos_t[c[v.t][j].first].begin();
int val = tr[c[v.t][j].first].read(idx2);
res[c[v.t][j].second] += (ll)(idx2 - val);
}
}
}
vector<point> upper1, upper2;
vector<point> lower1, lower2;
int main() {
#ifdef debug
clock_t tStart = clock();
freopen("/home/ssnsarang/Projects/OJUZ/JOI17_dragon2/inp.txt", "rt", stdin);
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
dragon.resize(n), dragon2.resize(n);
for (int i = 0; i < n; ++i) {
cin >> dragon[i].x >> dragon[i].y >> dragon[i].t;
dragon[i].idx = i;
}
cin >> human1.x >> human1.y >> human2.x >> human2.y;
//move the coordinates
if (human1.y > human2.y) swap(human1, human2);
mid = human1;
human2.x -= mid.x, human2.y -= mid.y;
human1 = point(-human2.x, -human2.y, 0, 0);
for (int i = 0; i < n; ++i) {
dragon[i].x -= mid.x;
dragon[i].y -= mid.y;
}
mid = point(0, 0, 0, 0);
cin >> q;
for (int i = 1; i <= m; ++i) {
b[i].clear();
c[i].clear();
}
for (int i = 0, x, y; i < q; ++i) {
cin >> x >> y;
b[x].push_back(ii(y, i));
}
for (int i = 1; i <= m; ++i) {
if (SZ(b[i]) > SQ) {
for (int j = 0; i < SZ(b[i]); ++j) {
c[b[i][j].first].push_back(ii(i, b[i][j].second));
}
b[i].clear();
}
}
solve(-1, -1);
solve(-1, 1);
for (int i = 0; i < n; ++i) {
dragon2[i].x = dragon[i].x - human2.x;
dragon2[i].y = dragon[i].y - human2.y;
dragon2[i].idx = dragon[i].idx;
dragon2[i].t = dragon[i].t;
}
point pt_tmp1 = human1, pt_tmp2 = human2;
human1 = point(mid.x - human2.x, mid.y - human2.y, 0, 0);
human2 = point(-human1.x, -human1.y, 0, 0);
dragon.swap(dragon2);
solve(1, -1);
solve(1, 1);
dragon.swap(dragon2);
point pt_tmp3 = human1, pt_tmp4 = human2;
auto something = [] (vector<point> &re, const vector<point> &src, bool mode) {
for (int i = 0; i < SZ(src); ++i) {
const point &v = src[i];
if (ccw(human2, v, human1) == mode) {
re.push_back(v);
}
}
};
human1 = pt_tmp1, human2 = pt_tmp2;
something(upper1, dragon, 1);
something(lower2, dragon, 0);
human1 = pt_tmp3, human2 = pt_tmp4;
something(upper2, dragon2, 1);
something(lower1, dragon2, 0);
solve2(upper1, upper2);
solve2(lower1, lower2);
for (int i = 0; i < q; ++i) {
cout << res[i] << "\n";
}
#ifdef debug
cout << "Total time: " << (int)(1000.0 * (double)(clock() - tStart) / CLOCKS_PER_SEC) << "ms\n";
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
8740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
