Submission #173503

#	Time	Username	Problem	Language	Result	Execution time	Memory
173503		jhwest2	별자리 2 (JOI14_constellation2)	C++14	100 / 100	4048 ms	247612 KiB

constellation2

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct Vec {
	ll x, y, c, i;

	Vec operator-(Vec a) {
		return {x-a.x, y-a.y};
	}
	ll operator*(Vec a) {
		return x*a.y - y*a.x;
	}
};

int N;
ll Lcnt[5000050][3], Rcnt[5000050][3];
Vec A[3030];
vector<Vec> pt[3];
vector<pii> v;

void solve(int t) {
	sort(pt[t].begin(), pt[t].end(), [&](Vec a, Vec b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});

	int idx[3030]; memset(idx, 0, sizeof idx);
	for (int i=0; i<pt[t].size(); i++) {
		idx[pt[t][i].i] = i;
	}
	for (int i=0; i<v.size(); i++) {
		int a = v[i].va, b = v[i].vb;
		Vec d = A[b] - A[a];

		int lo = 0, hi = pt[t].size();
		while (lo<hi) {
			int mid = lo+hi+1>>1;
			Vec x = pt[t][mid-1] - A[a];

			if (d*x < 0) lo = mid;
			else hi = mid-1;
		}
		Lcnt[i][t] = lo;

		lo = 0, hi = pt[t].size();
		while (lo<hi) {
			int mid = lo+hi>>1;
			Vec x = pt[t][mid] - A[a];

			if (d*x > 0) hi = mid;
			else lo = mid+1;
		}
		Rcnt[i][t] = pt[t].size() - lo;

		if (A[a].c != t || A[b].c != t) continue;
		swap(pt[t][idx[A[a].i]], pt[t][idx[A[b].i]]);
		swap(idx[A[a].i], idx[A[b].i]);
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> N;
	for (int i=0; i<N; i++) {
		cin >> A[i].x >> A[i].y >> A[i].c; A[i].i = i;
		pt[A[i].c].push_back(A[i]);
	}

	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			if (i == j) continue;
			if (A[i].x < A[j].x) v.push_back({i, j});
			if (A[i].x == A[j].x && A[i].y < A[j].y) v.push_back({i, j});
		}
	}
	sort(v.begin(), v.end(), [&](pii a, pii b) {
		Vec p = A[a.vb] - A[a.va];
		Vec q = A[b.vb] - A[b.va];
		ll t = p*q;
		return t>0;
	});
	for (int i=0; i<3; i++) solve(i);

	ll ans = 0;
	for (int i=0; i<v.size(); i++) {
		int p = A[v[i].va].c, q = A[v[i].vb].c;
		ll lp=1, rp=1, lq=1, rq=1;
		for (int j=0; j<3; j++) {
			if (j != p) lp *= Lcnt[i][j], rp *= Rcnt[i][j];
			if (j != q) lq *= Lcnt[i][j], rq *= Rcnt[i][j];
		}

		ans += lp*rq + rp*lq;
	}
	cout << ans/2;
}

Compilation message (stderr)

constellation2.cpp: In function 'void solve(int)':
constellation2.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<pt[t].size(); i++) {
                ~^~~~~~~~~~~~~
constellation2.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~
constellation2.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo+hi+1>>1;
              ~~~~~^~
constellation2.cpp:51:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo+hi>>1;
              ~~^~~
constellation2.cpp: In function 'int main()':
constellation2.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~

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