oj.uz

Submission #753545

# Submission time Handle Problem Language Result Execution time Memory
753545 2023-06-05T13:38:33 Z minhcool Ideal city (IOI12_city) C++17
100 / 100
 55 ms 18148 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 4 ms 7504 KB Output is correct
8 Correct 4 ms 7364 KB Output is correct
9 Correct 4 ms 7364 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8808 KB Output is correct
2 Correct 12 ms 8932 KB Output is correct
3 Correct 25 ms 10852 KB Output is correct
4 Correct 24 ms 10916 KB Output is correct
5 Correct 48 ms 14140 KB Output is correct
6 Correct 47 ms 14224 KB Output is correct
7 Correct 50 ms 14444 KB Output is correct
8 Correct 45 ms 14164 KB Output is correct
9 Correct 43 ms 14532 KB Output is correct
10 Correct 48 ms 18148 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9360 KB Output is correct
2 Correct 14 ms 9232 KB Output is correct
3 Correct 28 ms 12076 KB Output is correct
4 Correct 28 ms 11688 KB Output is correct
5 Correct 55 ms 16972 KB Output is correct
6 Correct 52 ms 15272 KB Output is correct
7 Correct 55 ms 17020 KB Output is correct
8 Correct 48 ms 15296 KB Output is correct
9 Correct 51 ms 14888 KB Output is correct
10 Correct 48 ms 14896 KB Output is correct