Submission #132880

#	Time	Username	Problem	Language	Result	Execution time	Memory
132880		arthurconmy	Ideal city (IOI12_city)	C++14	0 / 100	17 ms	3192 KiB

city

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN=100001;
const int INF=2147483647;
const int p2=131077;

int X_raw[MAXN];
int Y_raw[MAXN];

ll X[p2+p2+1];
ll Y[p2+p2+1];

ll query(int l, int r, bool is_x)
{
	l += p2-1;
	r += p2-1;

	ll ans=0;

	while(l<=r)
	{
		if(l%2 == 1)
		{
			if(is_x) ans += X[l++];
			else ans += Y[l++];
		}

		if(r%2 == 0)
		{
			if(is_x) ans += X[r--];
			else ans += Y[r--];
		}

		l/=2;
		r/=2;
	}

	return ans;
}

int DistanceSum(int N, int *X_coords, int *Y_coords)
{
	int min_x = INF;
	int min_y = INF;

	for(int i=0; i<N; i++)
	{
		min_x=min(min_x,X_coords[i]);
		min_y=min(min_y,Y_coords[i]);
	}

	for(int i=0; i<N; i++)
	{
		X_raw[X_coords[i]-min_x+1]++;
		Y_raw[Y_coords[i]-min_y+1]++;
	}

	for(int i=1; i<=N; i++) // indexing here is ... eek
	{
		X[p2-1+i] = ll(X_raw[i])*ll(i);
		Y[p2-1+i] = ll(Y_raw[i])*ll(i);
	}

	for(int i=p2-1; i>=1; i--)
	{
		X[i] = X[i+i] + X[i+i+1];
		Y[i] = Y[i+i] + Y[i+i+1];
	}

	ll ans = 0;

	vector<int> X_sorted;
	vector<int> Y_sorted;

	for(int i=0; i<N; i++)
	{
		X_sorted.push_back(X_coords[i]);
		Y_sorted.push_back(Y_coords[i]);
	}

	sort(X_sorted.begin(),X_sorted.end());
	sort(Y_sorted.begin(),Y_sorted.end());

	for(int i=0; i<N; i++)
	{
		int x = X_coords[i]-min_x+1;
		int y = Y_coords[i]-min_y+1;
	
		int x_before = lower_bound(X_sorted.begin(),X_sorted.end(),X_coords[i])-X_sorted.begin();
		ans += ll(x)*ll(x_before) - query(1,x-1,1);

		int y_before = lower_bound(Y_sorted.begin(),Y_sorted.end(),Y_coords[i])-Y_sorted.begin();
		ans += ll(y)*ll(y_before) - query(1,y-1,0);
	}

	return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45