Submission #23664

# Submission time Handle Problem Language Result Execution time Memory
23664 2017-05-18T11:50:21 Z Hiasat Ideal city (IOI12_city) C++14
0 / 100
13 ms 3548 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll res = 0;
void sum(vector<ll> &x, vector<ll> &preX, int X) {
	int idx = lower_bound(x.begin(), x.end(), X) - x.begin();
	if (idx) {
		res += (idx + 1) * X - preX[idx];
	}
	if (idx != preX.size()) {
		res += (preX.back() - (!idx?0:preX[idx - 1])) - (preX.size() - idx) * X;
	}
	res %= 1000000000;
}
vector<ll> preX, preY, x, y;

int DistanceSum(int N, int *X, int *Y) {
	for (int i = 0; i < N; ++i) {
		preX.push_back(X[i]);
		x.push_back(X[i]);
	}
	for (int i = 0; i < N; ++i) {
		preY.push_back(Y[i]);
		y.push_back(Y[i]);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(preX.begin(), preX.end());
	sort(preY.begin(), preY.end());
	for (int i = 1 ; i < preX.size(); ++i) {
		preX[i] += preX[i - 1];
	}
	for (int i = 1 ; i < preY.size(); ++i) {
		preY[i] += preY[i - 1];
	}
	for (int i = 0 ; i < N ; i++) {
		sum(x,preX,X[i]);

		sum(y,preY,Y[i]);		
	}
	return res/2;
}

Compilation message

city.cpp: In function 'void sum(std::vector<long long int>&, std::vector<long long int>&, int)':
city.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (idx != preX.size()) {
          ^
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < preX.size(); ++i) {
                     ^
city.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < preY.size(); ++i) {
                     ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 13 ms 3548 KB Output is correct
2 Incorrect 9 ms 3548 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3548 KB Output isn't correct
2 Halted 0 ms 0 KB -