Submission #705639

#	Time	Username	Problem	Language	Result	Execution time	Memory
705639		GusterGoose27	Dragon 2 (JOI17_dragon2)	C++17	0 / 100	194 ms	13176 KiB

dragon2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long double, int> pdi;

pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

pii operator-(pii a, pii b) {
	return pii(a.first-b.first, a.second-b.second);
}

ll operator*(pii a, pii b) {
	return (ll)a.first*b.second-(ll)a.second*b.first;
}

ll dot(pii a, pii b) {
	return (ll)a.first*b.first+(ll)a.second*b.second;
}

ld mag(pii a) {
	return sqrt(dot(a, a));
}

ld getang(pii a, pii b) { // returns cos theta*mag(b)
	return dot(a, b)/mag(a)/mag(b);
}

const int MAXN = 3000; // should be 3e4
const int BLOCK = 1; // should be 100
const int MAXBLOCKS = MAXN/BLOCK;
int n, m, q;
vector<int> big_groups;
int big_inv[MAXN];
ll num[MAXBLOCKS][MAXN];
pii points[MAXN];
vector<int> in_group[MAXN];
int id[MAXN];
pii p1, p2;
vector<int> points_sorted[2][2]; // up or down, sorted by costheta of p1 or p2
int points_sorted_inv[2][MAXN]; // no reason to consider top or bottom, we are already going to know the side
vector<int> group_sort[MAXN][2][2];
int bit[MAXN];

void ins(int p, int v) {
	for (; p < n; p |= (p+1)) bit[p] += v;
}

int sum(int p) {
	int s = 0;
	for (p++; p > 0; p &= (p-1)) s += bit[p-1];
	return s;
}

pii base, comp_vec;

struct comp {
	bool operator()(int a, int b) {
		return getang(comp_vec, points[a]-base) < getang(comp_vec, points[b]-base);
	}
} comp;

void make_num(int p, ll ans[]) {
	for (int j = 0; j < 2; j++) {
		if (j == 0) {
			base = p1;
			comp_vec = p2-p1;
		}
		else {
			base = p2;
			comp_vec = p1-p2;
		}
		vector<ld> updates;
		int num = group_sort[p][j^1][j].size();
		for (int v: group_sort[p][j^1][j]) { // iterating over points of type p on the other side sorted by the first point sweeping left to righ
			updates.push_back(getang(comp_vec, base-points[v])); // negative
		}
		int m = points_sorted[j][j].size();
		int k = 0;
		for (int i = 0; i < m; i++) { // iterating over all points not of type p on this side sorted by the left point angle left to right
			int cur = points_sorted[j][j][i];
			if (id[cur] == p) continue;
			while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
			ans[id[cur]] += k-num;
		}
		updates.clear();
		base = p1+p2-base;
		for (int v: group_sort[p][j^1][j^1]) { // type p, opposite side, right point, sweeping left to right
			updates.push_back(getang(comp_vec, base-points[v])); // positive
		}
		k = 0;
		for (int i = 0; i < m; i++) { // not of type p, this side, right point, sweeping left to right
			int cur = points_sorted[j][j^1][i];
			if (id[cur] == p) continue;
			while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
			ans[id[cur]] += num-k;
		}
		fill(bit, bit+n, 0);
		m = points_sorted[j][j].size();
		k = 0;
		updates.clear();
		base = p1+p2-base;
		for (int v: group_sort[p][j][j]) updates.push_back(getang(comp_vec, points[v]-base));
		// updates is full of things sweeping from left to right on top with respect to left point
		for (int i = 0; i < m; i++) { // sweep left to right from bottom pov, second point, on the bottom
			int cur = points_sorted[j][j][i];
			if (id[cur] == p) continue;
			while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) {
				int mn = -1;
				int mx = m; // which points have we passed
				int v = group_sort[p][j][j][k];
				ld comp_ang = getang(comp_vec, points[v]-(p1+p2-base));
				while (mx > mn+1) {
					int mid = (mn+mx)/2;
					int mpoint = points_sorted[j][j^1][mid];
					if (getang(comp_vec, points[mpoint]-(p1+p2-base)) < comp_ang) mn = mid;
					else mx = mid;
				}
				ins(0, 1);
				ins(mx, -1);
				k++;
			}
			ans[id[cur]] += sum(points_sorted_inv[j^1][cur]);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> points[i].first >> points[i].second >> id[i];
		id[i]--;
		in_group[id[i]].push_back(i);
	}
	cin >> p1.first >> p1.second >> p2.first >> p2.second;
	for (int i = 0; i < m; i++) {
		if (in_group[i].size() >= BLOCK) {
			big_groups.push_back(i);
		}
		for (int v: in_group[i]) {
			bool b = (p2-p1)*(points[v]-p1) < 0;
			for (int j = 0; j < 2; j++) {
				group_sort[i][b][j].push_back(v);
				points_sorted[b][j].push_back(v);
			}
		}
		base = p1;
		comp_vec = p2-p1;
		sort(group_sort[i][0][0].begin(), group_sort[i][0][0].end(), comp);
		base = p2;
		sort(group_sort[i][0][1].begin(), group_sort[i][0][1].end(), comp);
		comp_vec = p1-p2;
		sort(group_sort[i][1][1].begin(), group_sort[i][1][1].end(), comp);
		base = p1;
		sort(group_sort[i][1][0].begin(), group_sort[i][1][0].end(), comp);
	}
	base = p1;
	comp_vec = p2-p1;
	sort(points_sorted[0][0].begin(), points_sorted[0][0].end(), comp);
	base = p2;
	sort(points_sorted[0][1].begin(), points_sorted[0][1].end(), comp);
	comp_vec = p1-p2;
	sort(points_sorted[1][1].begin(), points_sorted[1][1].end(), comp);
	base = p1;
	sort(points_sorted[1][0].begin(), points_sorted[1][0].end(), comp);
	for (int j = 0; j < 2; j++) {
		for (int k = 0; k < 2; k++) {
			for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i;
		}
	}
	for (int i = 0; i < big_groups.size(); i++) {
		make_num(big_groups[i], num[i]);
		big_inv[big_groups[i]] = i;
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		if (in_group[x].size() >= BLOCK) {
			cout << num[big_inv[x]][y] << "\n";
		}
		else { // deal with this later

		}
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'void make_num(int, ll*)':
dragon2.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) {
      |           ~~^~~~~~~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |    for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i;
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |  for (int i = 0; i < big_groups.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~

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