Submission #753545

#	Time	Username	Problem	Language	Result	Execution time	Memory
753545		minhcool	Ideal city (IOI12_city)	C++17	100 / 100	55 ms	18148 KiB

city

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

ll n;

ll x[N], y[N], answer;

namespace cal{
	vector<ll> Adj[N];
	ll sz[N], szz[N];
	struct comp{
		ll st, en, rw;
		comp(ll _rw, ll _st, ll _en): rw(_rw), st(_st), en(_en){}
	};
	vector<comp> comps;
	void dfs(ll u, ll p){
		sz[u] = comps[u].en - comps[u].st + 1;
		for(auto v : Adj[u]){
			if(v == p) continue;
			dfs(v, u);
			sz[u] += sz[v];
		}
//		cout << "HELLO" <<  u << " " << sz[u] << "\n";
		answer += sz[u] * (n - sz[u]);
	}
	void process(){
		for(int i = 0; i <= n; i++){
			Adj[i].clear();
			comps.clear();
		}
		vector<ii> polls;
		for(ll i = 0; i < n; i++) polls.pb({x[i], y[i]});
		sort(polls.begin(), polls.end());
		polls.pb({oo, oo});
		//exit(0);
		ii lst = polls[0];
		assert(polls.size() == (n + 1));
		for(ll i = 1; i <= n; i++){
		//	cout << polls[i].fi << " " << polls[i].se << "\n";
			if(polls[i] != mp(polls[i - 1].fi, polls[i - 1].se + 1)){
				comps.pb({polls[i - 1].fi, lst.se, polls[i - 1].se});
	//			cout << polls[i - 1].fi << " " << lst.se << " " << polls[i - 1].se << "\n";
				lst = polls[i];
			}
		}
	//	cout << "OKAY\n";
		//exit(0);
		ll itr = 0;
		for(ll i = 0; i < comps.size(); i++){
			while(itr < comps.size() && ((comps[itr].rw <= comps[i].rw) || ((comps[itr].rw == (comps[i].rw + 1)) && (comps[itr].en < comps[i].st)))) itr++;
			ll temp = itr;
			while(temp < comps.size()){
				if(comps[temp].rw > (comps[i].rw + 1)) break;
				if(comps[temp].st > comps[i].en) break;
	//			cout << i << " " << temp << "\n";
				Adj[i].pb(temp);
				Adj[temp].pb(i);
 				temp++;
			}
		}
		//exit(0);
		dfs(0, 0);
	}
}

int DistanceSum(int N, int *X, int *Y){
	n = N;
	for(ll i = 0; i < n; i++){
		x[i] = X[i], y[i] = Y[i];
	}
	cal::process();
	for(ll i = 0; i < n; i++) swap(x[i], y[i]);
	cal::process();
	return (int)(answer % (ll)1000000000);
}

Compilation message (stderr)

city.cpp: In constructor 'cal::comp::comp(long long int, long long int, long long int)':
city.cpp:28:14: warning: 'cal::comp::rw' will be initialized after [-Wreorder]
   28 |   ll st, en, rw;
      |              ^~
city.cpp:28:6: warning:   'long long int cal::comp::st' [-Wreorder]
   28 |   ll st, en, rw;
      |      ^~
city.cpp:29:3: warning:   when initialized here [-Wreorder]
   29 |   comp(ll _rw, ll _st, ll _en): rw(_rw), st(_st), en(_en){}
      |   ^~~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from city.cpp:2:
city.cpp: In function 'void cal::process()':
city.cpp:53:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   53 |   assert(polls.size() == (n + 1));
      |          ~~~~~~~~~~~~~^~~~~~~~~~
city.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cal::comp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(ll i = 0; i < comps.size(); i++){
      |                 ~~^~~~~~~~~~~~~~
city.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cal::comp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    while(itr < comps.size() && ((comps[itr].rw <= comps[i].rw) || ((comps[itr].rw == (comps[i].rw + 1)) && (comps[itr].en < comps[i].st)))) itr++;
      |          ~~~~^~~~~~~~~~~~~~
city.cpp:68:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cal::comp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    while(temp < comps.size()){
      |          ~~~~~^~~~~~~~~~~~~~

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