oj.uz

Submission #132881

# Submission time Handle Problem Language Result Execution time Memory
132881 2019-07-19T21:27:30 Z arthurconmy Ideal city (IOI12_city) C++14
23 / 100
 90 ms 6768 KB 
#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%1000000000LL;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3192 KB Output is correct
2 Correct 16 ms 3320 KB Output is correct
3 Correct 43 ms 4724 KB Output is correct
4 Correct 38 ms 4596 KB Output is correct
5 Correct 84 ms 6640 KB Output is correct
6 Correct 78 ms 6636 KB Output is correct
7 Correct 90 ms 6644 KB Output is correct
8 Correct 80 ms 6580 KB Output is correct
9 Correct 71 ms 6516 KB Output is correct
10 Correct 71 ms 6768 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3244 KB Output isn't correct
2 Halted 0 ms 0 KB -