oj.uz

Submission #173503

# Submission time Handle Problem Language Result Execution time Memory
173503 2020-01-04T10:05:25 Z jhwest2 별자리 2 (JOI14_constellation2) C++14
100 / 100
 4048 ms 247612 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 7 ms 1144 KB Output is correct
5 Correct 11 ms 1664 KB Output is correct
6 Correct 25 ms 3064 KB Output is correct
7 Correct 24 ms 3064 KB Output is correct
8 Correct 23 ms 3068 KB Output is correct
9 Correct 22 ms 2932 KB Output is correct
10 Correct 17 ms 2172 KB Output is correct
11 Correct 25 ms 3064 KB Output is correct
12 Correct 24 ms 3064 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 18120 KB Output is correct
2 Correct 228 ms 22848 KB Output is correct
3 Correct 345 ms 27996 KB Output is correct
4 Correct 347 ms 27908 KB Output is correct
5 Correct 871 ms 62268 KB Output is correct
6 Correct 1311 ms 110268 KB Output is correct
7 Correct 2649 ms 172056 KB Output is correct
8 Correct 3717 ms 247612 KB Output is correct
9 Correct 4038 ms 247340 KB Output is correct
10 Correct 4048 ms 247536 KB Output is correct
11 Correct 4009 ms 247452 KB Output is correct
12 Correct 3232 ms 247252 KB Output is correct
13 Correct 3588 ms 247364 KB Output is correct
14 Correct 4003 ms 247348 KB Output is correct
15 Correct 4008 ms 247188 KB Output is correct
16 Correct 3467 ms 247300 KB Output is correct