Submission #134139

#	Time	Username	Problem	Language	Result	Execution time	Memory
134139		AngusRitossa	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1411 ms	12512 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
	#define D(x...) printf(x)
#else	
	#define D(x...)
#endif
typedef long long ll;
int n, m, g[30010], isbelow[30010], num1[30010], num2[30010];
vector<int> group[30010], ag[30010], bg[30010];
ll x[30010], y[30010];
pair<ll, ll> s, e;
ll cross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c)
{
	a.first -= c.first, b.first -= c.first;
	a.second -= c.second, b.second -= c.second;
	return a.first*b.second - a.second*b.first;
}
void findids(bool rev, pair<ll, ll> s, pair<ll, ll> e, int* num)
{
	// separate into left and right
	vector<pair<pair<ll, ll>, int> > below;
	for (int i = 0; i < n; i++)
	{
		pair<ll, ll> other = { x[i] + 2ll*(s.first-x[i]), y[i] + 2ll*(s.second-y[i]) };
	//	D("%lld %lld\n", other.first, other.second);
		if (cross(s, {x[i], y[i]}, e) < 0) 
		{
			if (rev) below.push_back({other, i});
			else isbelow[i] = 1, below.push_back({{ x[i], y[i] }, i });
		}
		else
		{
			if (!rev) below.push_back({other, i});
			else isbelow[i] = 1, below.push_back({{ x[i], y[i] }, i });
		}
//		D("%d: isbelow %d\n", i, isbelow[i]);
	}
	sort(below.begin(), below.end(), [s](const pair<pair<ll, ll>, int> &a, const pair<pair<ll, ll>, int> &b)
	{
		return cross(a.first, b.first, s) < 0;
	});
	if (rev) reverse(below.begin(), below.end());
//	for (auto b : below) D("%d ", b.second);
//	D(" -- below\n");
	for (int i = 0; i < (int)below.size(); i++) num[below[i].second] = i;
}
struct Node
{
	int val, left, right;
};
int upto;
Node rangetree[30010*40];
void update(int node, int curr, int oldcurr, int cstart = 0, int cend = 30010)
{
	rangetree[curr].val = rangetree[oldcurr].val;
	if (cstart == cend)
	{
		rangetree[curr].val++;
		return;
	}
	int mid = (cstart+cend)/2;
	if (node <= mid)
	{
		rangetree[curr].left = ++upto;
		rangetree[curr].right = rangetree[oldcurr].right;
		update(node, rangetree[curr].left, rangetree[oldcurr].left, cstart, mid);
	}
	else
	{
		rangetree[curr].right = ++upto;
		rangetree[curr].left = rangetree[oldcurr].left;
		update(node, rangetree[curr].right, rangetree[oldcurr].right, mid+1, cend);
	}
	rangetree[curr].val = rangetree[rangetree[curr].left].val + rangetree[rangetree[curr].right].val;
}
int query(int s, int e, int curr, int cstart = 0, int cend = 30010)
{
	if (s <= cstart && cend <= e) return rangetree[curr].val;
	int mid = (cstart+cend)/2;
	if (e <= mid) return query(s, e, rangetree[curr].left, cstart, mid);
	else if (s > mid) return query(s, e, rangetree[curr].right, mid+1, cend);
	else return query(s, e, rangetree[curr].left, cstart, mid) + query(s, e, rangetree[curr].right, mid+1, cend);
}
int root[30010];
int aminlower(vector<int>&v, int x, int y, int l = 0)
{
	if (v.empty()) return 0;
	if (x < num1[v[0]]) return 0;
	int s = 0;
	int e = v.size()-1;
	while (s < e)
	{
		int m = (s+e+1)/2;
		if (num1[v[m]] > x) e = m-1;
		else s = m;
	}
	return query(l, y, root[v[s]]);
}
int aminupper(vector<int> &v, int x, int y)
{
	return aminlower(v, 1e9, 30010, y) - aminlower(v, x-1, 30010, y);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld%lld%d", &x[i], &y[i], &g[i]);
		group[g[i]].push_back(i);
	}
	scanf("%lld%lld%lld%lld", &s.first, &s.second, &e.first, &e.second);
	findids(0, e, s, num1);
	findids(1, s, e, num2);
	for (int i = 1; i <= m; i++)
	{
		for (auto a : group[i])
		{
			if (isbelow[a]) bg[i].push_back(a);
			else ag[i].push_back(a);
		}
		sort(bg[i].begin(), bg[i].end(), [](const int &a, const int &b) { return num1[a] < num1[b]; });
		sort(ag[i].begin(), ag[i].end(), [](const int &a, const int &b) { return num1[a] < num1[b]; });
		int r = 0;
		for (auto a : ag[i])
		{
			root[a] = ++upto;
			update(num2[a], root[a], r);
			r = root[a];
		}
		r = 0;
		for (auto a : bg[i])
		{
			root[a] = ++upto;
			update(num2[a], root[a], r);
			r = root[a];
		}
	}
	int q;
	scanf("%d", &q);
	for (int query = 0; query < q; query++)
	{
		int i, j;
		scanf("%d%d", &i, &j);
		ll ans = 0;
		if (group[i].size() < group[j].size())
		{	
			for (auto a : group[i])
			{
				D("checking %d\n", a);
				ans += aminupper(bg[j], num1[a], num2[a]);
				ans += aminlower(ag[j], num1[a], num2[a]);
			}
		}
		else
		{
			for (auto a : group[j])
			{
				D("checking %d\n", a);
				if (isbelow[a])
				{
					ans += aminlower(bg[i], num1[a], num2[a]);
					ans += aminlower(ag[i], num1[a], num2[a]);
				}
				else
				{
					ans += aminupper(bg[i], num1[a], num2[a]);
					ans += aminupper(ag[i], num1[a], num2[a]);
				}
			}
		}
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d", &x[i], &y[i], &g[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &s.first, &s.second, &e.first, &e.second);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
dragon2.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &i, &j);
   ~~~~~^~~~~~~~~~~~~~~~

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