Submission #33640

#	Time	Username	Problem	Language	Result	Execution time	Memory
33640		sinhriv	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	73 ms	152108 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

struct Point{
	int x;
	int y;

	void read(){
		char read[5];
		scanf("%s%d", read, &y);
		x = (read[0] - 'A');
	}
};	

struct Person{
	Point u;
	Point v;

	bool check(){
		u.read();
		v.read();
		return (u.x == v.x);
	}

	int calc(int val){
		return abs(u.y - val) + abs(v.y - val);
	}
};

vector < pair < int, int > > a;

long long One(){
	if(a.size() == 0) return 0;
	int n = a.size();
	vector < int > lst;

	for(int i = 0; i < n; ++i){
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);
	}

	sort(lst.begin(), lst.end());

	long long ans = 0;


	for(int i = 0; i < n + n; ++i){
		ans += abs(lst[i] - lst[n]);
	}
	return ans + n; 
}

struct lex_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.first + x.second == y.first + y.second) {
  		if(x.first == y.first) return x.second < y.second;
  		return x.first < y.first;
  	}
  	return x.first + x.second < y.first + y.second;
  }
};


struct second_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.second != y.second) return x.second  < y.second;
  	return x.first < y.first;
  }
};

const int N = 2e5 + 10;

long long prefix[N];

int calc(pair < int, int > p, int val){
	return abs(p.first - val) + abs(p.second - val);
}

long long Two(){
	int n = a.size();
	if(n == 0) return 0;

	vector < int > lst;

	for(int i = 0; i < n; ++i){
		if(a[i].first > a[i].second){
			swap(a[i].first, a[i].second);
		}
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);

	}

	sort(a.begin(), a.end());
	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());

	for(int i = 0; i < n; ++i){
		prefix[i] = a[i].first + a[i].second;
		if(i > 0) prefix[i] += prefix[i - 1];
	}

	int small = 0;

	long long sum = 0;
	long long total = 0;
	
	long long ans = 1e18;

	multiset < int > tree;



	for(int i = 0; i < lst.size(); ++i){
		int x = lst[i];
		while(small < n && a[small].first <= x){
			sum += a[small].second;
			total += a[small].first;
			tree.insert(a[small].second);
			++small;
		}
		while(!tree.empty() && *tree.begin() <= x){
			sum -= *tree.begin() * 2;
			tree.erase(tree.begin());
		}


		long long now = (1LL * small * x - total) + (sum + 1LL * (small - 2LL * tree.size()) * x);
	
		multiset < pair < int, int >, lex_compare > inside;	
		multiset < pair < int, int >, second_compare > big;
		
		long long sumBigX = 0;
		long long sumBigY = 0;
		long long sumInsideX = 0;
		long long sumInsideY = 0;
		long long sumOutside = 0;

		int pter = small;		
		for(int j = i + 1; j < lst.size(); ++j){
			int y = lst[j];
			int where = lower_bound(a.begin(), a.end(), make_pair(y, 0)) - a.begin();

			long long most = prefix[n - 1] - (where > 0 ? prefix[where - 1] : 0) - 2LL * (n - where) * y;

			
			while(pter < where){
				if(a[pter].second >= y){
					big.insert(a[pter]);
					sumBigX += a[pter].first;
					sumBigY += a[pter].second;
				}
				else{
					inside.insert(a[pter]);
					sumInsideX += a[pter].first;
					sumInsideY += a[pter].second;
				}
				++pter;
			}
			
			while(!big.empty() && big.begin() -> second < y){
				sumBigX -= big.begin() -> first;
				sumBigY -= big.begin() -> second;


				sumInsideX += big.begin() -> first;
				sumInsideY += big.begin() -> second;
				inside.insert(*big.begin());
				big.erase(big.begin());
			}

			while(!inside.empty()){
				auto p = *inside.begin();
				if(p.first + p.second <= x + y){
					sumInsideX -= p.first;
					sumInsideY -= p.second;
					sumOutside += calc(p, x);
					inside.erase(inside.begin());
					continue;
				}
				break; 
			}
			ans = min(ans, 2LL * int(inside.size()) * y - sumInsideY - sumInsideX + sumOutside + sumBigY - sumBigX + most + now);
     
		}
	}


	return n + ans;
}

long long preCalc[N];

struct PersistentIT{
	int cnt, root, n;
	int L[N * 10];
	int R[N * 10];
	vector < pair < int, int > > save;
	pair < long long, int > value[N * 10];

	#define mid ((l + r) >> 1)

	void build(int &x, int l, int r){
		if(x == 0) x = ++cnt;
		if(l == r) {
			value[x] = make_pair(0, 0);
			return;
		}
		build(L[x], l, mid);
		build(R[x], mid + 1, r);
	}	

	pair < int, int > combine(pair < int, int > u, pair < int, int > v){
		u.first += v.first;
		u.second += v.second;
		return u;
	}


	void upd(int &x, int old, int l, int r, int pos, pair < int, int > val){
		if(l > pos || r < pos){
			x = old;
			return;
		}
		x = ++cnt;
		value[x] = combine(value[old], val);
		if(l == r){
			return;
		}
		upd(L[x], L[old], l, mid, pos, val);
		upd(R[x], R[old], mid + 1, r, pos, val);
		value[x] = combine(value[L[x]], value[R[x]]);
	}


	pair < int, int > sub(pair < int, int > u, pair < int, int > v){
		u.first -= v.first;
		u.second -= v.second;
		return u;
	}

	pair < int, int > query(int x, int l, int r, int u, int v){
		if(l > v || r < u){
			return make_pair(0, 0);
		}
		if(l >= u && r <= v) {
			return value[x];
		}
		return combine(query(L[x], l, mid, u, v), query(R[x], mid + 1, r, u, v));
	}

	void add(int x){
		save.emplace_back(x, root);
	}


	void Init(int sz){
		n = sz;
		cnt = root = 1;
		build(root, 1, n);
		add(0);
	}

	void update(int pos, int val){
		upd(root, root, 1, n, pos, make_pair(val, 1));
	}

	pair < int, int > ask(int x, int l, int r){
		if(x < 0) return make_pair(0, 0);
		return query(x, 1, n, l, r);
	}

	int fin(int x){

		int p = lower_bound(save.begin(), save.end(), make_pair(x, -1)) - save.begin();
		return save[p].second;
	}

	pair < int, int > query2D(int l, int r, int u, int v){
		++l; ++r;

		//cout << l << " " << r << " " << u << " " << v << endl;
		if(l > r || u > v) return make_pair(0, 0);
		return sub(ask(fin(r), u, v), ask(fin(l - 1), u, v));
	}
}treeInside, treeBig, treeSum;

vector < int > lst, arr;

int getIdx(int x){
	return lower_bound(lst.begin(), lst.end(), x) - lst.begin() + 1;
}

long long sumX[N];
long long sumY[N];

long long Calc(int x, int y){
	int pos = upper_bound(a.begin(), a.end(), make_pair(x + 1, -1)) - a.begin() - 1;
	long long now = preCalc[lower_bound(lst.begin(), lst.end(), x) - lst.begin()];


	int p = lower_bound(a.begin(), a.end(), make_pair(y, -1)) - a.begin();
	long long tot = prefix[a.size() - 1] - (p > 0 ? prefix[p - 1] : 0) - 2LL * (a.size() - p) * y;


	long long Outside = treeBig.query2D(pos + 1, p - 1, getIdx(y), lst.size()).first;



	auto current = treeInside.query2D(pos + 1, p - 1, 1, getIdx(x + y) - 1);


	long long solve = current.first - 2LL * current.second * x;

	auto smaller = treeSum.query2D(pos + 1, p - 1, getIdx(y), lst.size());


	long long other = sumX[p - 1] - sumX[pos] + sumY[p - 1] - sumY[pos];
	//cout << other - current.first - small<< endl;
	other = 2LL * (p - 1 - pos - current.second - smaller.second) * y - (other - current.first - smaller.first);


	return now + tot + Outside + solve + other;

}

long long Three(){
	int n = a.size();
	if(n == 0) return 0;


	for(int i = 0; i < n; ++i){
		if(a[i].first > a[i].second){
			swap(a[i].first, a[i].second);
		}
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);

	}

	sort(a.begin(), a.end());
	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());

	arr = lst;

	for(int i = 0; i < n; ++i){
		prefix[i] = a[i].first + a[i].second;
		if(i > 0) prefix[i] += prefix[i - 1];
	}

	int small = 0;

	long long sum = 0;
	long long total = 0;
	

	multiset < int > tree;


	for(int i = 0; i < lst.size(); ++i){
		int x = lst[i];
		while(small < n && a[small].first <= x){
			sum += a[small].second;
			total += a[small].first;
			tree.insert(a[small].second);
			++small;
		}
		while(!tree.empty() && *tree.begin() <= x){
			sum -= *tree.begin() * 2;
			tree.erase(tree.begin());
		}


		long long now = (1LL * small * x - total) + (sum + 1LL * (small - 2LL * tree.size()) * x);
		preCalc[i] = now;
	}	

	for(int i = 0; i < n; ++i){
		lst.push_back(a[i].first + a[i].second);
	}

	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());

	treeSum.Init(lst.size());
	treeBig.Init(lst.size());
	treeInside.Init(lst.size());


	for(int i = 0; i < n; ++i){
		treeSum.update(getIdx(a[i].second), a[i].first + a[i].second);
		treeBig.update(getIdx(a[i].second), a[i].second - a[i].first);

		//cout << getIdx(a[i].second) << " " << i + 1 << endl;

		treeInside.update(getIdx(a[i].first + a[i].second), a[i].first + a[i].second);

		treeBig.add(i + 1);
		treeSum.add(i + 1);
		treeInside.add(i + 1);

		sumX[i] = a[i].first;
		sumY[i] = a[i].second;

		if(i > 0){
			sumX[i] += sumX[i - 1];
			sumY[i] += sumY[i - 1];
		}
	}

	long long ans = 1e18;




	for(int i = 0; i < arr.size(); ++i){
		for(int j = i + 1; j < arr.size(); ++j){
			ans = min(ans, Calc(arr[i], arr[j]));
		}
	}
	return ans + n;
}	


int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	long long out = 0;

	int k, n;
	scanf("%d%d", &k, &n);

	for(int i = 1; i <= n; ++i){
		Person x;
		if(x.check()){
			out += x.calc(x.u.y);
		}
		else{
			a.emplace_back(x.u.y, x.v.y);
		}
	}


	if(k == 1) cout << One() + out;
	else{
		long long ans = One();
		if(a.size() <= 1000){
			ans = min(ans, Three());
		}
		else{
			ans = min(ans, Three());
		}

		cout << ans + out;
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int Two()':
bridge.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:141:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < lst.size(); ++j){
                        ^
bridge.cpp: In function 'long long int Three()':
bridge.cpp:362:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:418:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < arr.size(); ++i){
                   ^
bridge.cpp:419:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < arr.size(); ++j){
                        ^
bridge.cpp: In function 'int main()':
bridge.cpp:429:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
bridge.cpp:435:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^
bridge.cpp: In member function 'void Point::read()':
bridge.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", read, &y);
                          ^

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37