Submission #576685

#	Time	Username	Problem	Language	Result	Execution time	Memory
576685		benson1029	Ideal city (IOI12_city)	C++14	100 / 100	71 ms	39400 KiB

city

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

long long mod = 1e9;
vector<int> XX, YY;
int n;
vector<int> y[200005];
long long ans = 0;
vector< pair<long long,long long> > y_lst[200005];

long long calcarr(vector<long long> x, vector<long long> y) {
	long long rv = 0, sum1 = 0, sum2 = 0;
	for(int i=0; i<x.size(); i++) {
		rv += x[i] * y[i];
		sum1 += x[i];
		sum2 += y[i];
	}
	sum1 %= mod; sum2 %= mod; rv %= mod;
	return (sum1*sum2-rv) % mod;
}

long long calcarr2(vector<long long> x, vector<long long> y) {
	long long rv = 0;
	long long prevcount = 0, prevsum = 0;
	for(int i=0; i<x.size(); i++) {
		rv += ((prevcount * i - prevsum) % mod) * x[i];
		rv %= mod;
		prevcount += x[i];
		prevsum += i * x[i]; prevsum %= mod;
	}
	return rv;
}

pair< vector<long long>, vector<long long> > dfs(int x, int y, int px, int py) {
	vector<long long> rv, rvdis;
	long long tmpans = 0;
	rv.resize(y_lst[x][y].second - y_lst[x][y].first + 1);
	rvdis.resize(rv.size());
	for(int i=0; i<rv.size(); i++) rv[i] = 1;
	for(int i=0; i<rv.size(); i++) rvdis[i] = 0;
	auto process = [] (int nx, int x, int y, int px, int py, vector<long long> &rv, vector<long long> &rvdis, long long &tmpans) {
		int l = upper_bound(y_lst[nx].begin(), y_lst[nx].end(), make_pair(y_lst[x][y].first, y_lst[x][y].first)) - y_lst[nx].begin() - 1;
		if(l < 0) l = 0;
		int r = lower_bound(y_lst[nx].begin(), y_lst[nx].end(), make_pair(y_lst[x][y].second, y_lst[x][y].second)) - y_lst[nx].begin();
		if(r >= y_lst[nx].size()) r = y_lst[nx].size() - 1;
		for(int i=l; i<=r; i++) {
			if(!(y_lst[nx][i].first > y_lst[x][y].second || y_lst[nx][i].second < y_lst[x][y].first)) {
				if(!(px==nx && py==i)) {
					auto ttmp = dfs(nx, i, x, y);
					auto tmp = ttmp.first;
					auto tmpdis = ttmp.second;
					//tmpans -= calcarr(tmp, tmpdis);
					//tmpans %= mod;
					for(int j=0; j<tmp.size(); j++) {
						int AY = y_lst[nx][i].first + j;
						int BY = AY;
						if(BY > y_lst[x][y].second) BY = y_lst[x][y].second;
						if(BY < y_lst[x][y].first) BY = y_lst[x][y].first;
						tmpans += rvdis[BY - y_lst[x][y].first] * tmp[j] + rv[BY - y_lst[x][y].first] * (tmpdis[j] + tmp[j] * (1+abs(BY-AY)));
						tmpans %= mod;
					}
					int BYprev = -1;
					vector<long long> tmprv, tmprvdis;
					tmprv.clear(); tmprvdis.clear();
					for(int j=0; j<tmp.size(); j++) {
						int AY = y_lst[nx][i].first + j;
						int BY = AY;
						if(BY > y_lst[x][y].second) BY = y_lst[x][y].second;
						if(BY < y_lst[x][y].first) BY = y_lst[x][y].first;
						rv[BY - y_lst[x][y].first] += tmp[j];
						rvdis[BY - y_lst[x][y].first] += tmpdis[j] + tmp[j] * (1+abs(BY-AY));
						if(BYprev==-1 || BY!=BYprev) {
							BYprev = BY;
							tmprv.push_back(tmp[j]);
							tmprvdis.push_back(tmpdis[j] + tmp[j] * (1+abs(BY-AY)));
						} else {
							tmprv[tmprv.size()-1] += tmp[j];
							tmprvdis[tmprvdis.size()-1] += tmpdis[j] + tmp[j] * (1+abs(BY-AY));
						}
					}
					tmpans -= calcarr(tmprv, tmprvdis);
					tmpans -= calcarr2(tmprv, tmprvdis);
					tmpans %= mod;
				}
			}
		}
	};
	if(x>0) process(x-1, x, y, px, py, rv, rvdis, tmpans);
	process(x+1, x, y, px, py, rv, rvdis, tmpans);
	tmpans += calcarr(rv, rvdis);
	tmpans += calcarr2(rv, rvdis);
	tmpans %= mod;
	if(tmpans<0) tmpans+=mod;
	ans += tmpans;
	ans %= mod;
	return make_pair(rv, rvdis);
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	for(int i=0; i<N; i++) {
		XX.push_back(X[i]);
		YY.push_back(Y[i]);
	}
	sort(XX.begin(), XX.end());
	sort(YY.begin(), YY.end());
	for(int i=0; i<N; i++) {
		X[i] -= XX[0];
		Y[i] -= YY[0];
	}
	for(int i=0; i<N; i++) {
		y[X[i]].push_back(Y[i]);
	}
	for(int i=0; i<N; i++) {
		sort(y[i].begin(), y[i].end());
		for(int j:y[i]) {
			if(y_lst[i].size() > 0 && j == y_lst[i][y_lst[i].size()-1].second + 1) {
				y_lst[i][y_lst[i].size()-1].second++;
			} else {
				y_lst[i].push_back({j, j});
			}
		}
	}
	for(int i=0; i<N; i++) {
		if(y_lst[i].size()) {
			dfs(i, 0, -1, -1);
			goto end;
		}
	}
	end:;
	ans %= mod;
	if(ans<0) ans+=mod;
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'long long int calcarr(std::vector<long long int>, std::vector<long long int>)':
city.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0; i<x.size(); i++) {
      |               ~^~~~~~~~~
city.cpp: In function 'long long int calcarr2(std::vector<long long int>, std::vector<long long int>)':
city.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0; i<x.size(); i++) {
      |               ~^~~~~~~~~
city.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > dfs(int, int, int, int)':
city.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0; i<rv.size(); i++) rv[i] = 1;
      |               ~^~~~~~~~~~
city.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<rv.size(); i++) rvdis[i] = 0;
      |               ~^~~~~~~~~~
city.cpp: In lambda function:
city.cpp:45:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if(r >= y_lst[nx].size()) r = y_lst[nx].size() - 1;
      |      ~~^~~~~~~~~~~~~~~~~~~
city.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      for(int j=0; j<tmp.size(); j++) {
      |                   ~^~~~~~~~~~~
city.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      for(int j=0; j<tmp.size(); j++) {
      |                   ~^~~~~~~~~~~

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