Submission #45351

#	Time	Username	Problem	Language	Result	Execution time	Memory
45351		ssnsarang2023	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	386 ms	56856 KiB

dragon2

//#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;
vector<ii> b[N], c[N];
ll res[N*10], cnt[N];
vector<point> dragon, dragon2;
point human1, mid, human2;
vector<TData> g[178];
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 + 2);
		_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];

const int SQN = 173;

void solve(ll mul, ll mul2) {
	sort(dragon.begin(), dragon.end());
	for (int i = 0; i <= SQN+1; ++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 / SQN].push_back(TData(lo, hi, dragon[i].t));
		}
	}
	for (int i = 0; i <= SQN+1; ++i) {
		sort(g[i].begin(), g[i].end());
	}
	for (int i = 0; i <= SQN+1; ++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 < Lmax) {
				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 < Lmax) {
				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 (int i = 0; i < SZ(a1); ++i) {
		const point &v = a1[i];
		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("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 = 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; j < 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;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40