Submission #33657

#	Time	Username	Problem	Language	Result	Execution time	Memory
33657		sinhriv	Palembang Bridges (APIO15_bridge)	C++14	63 / 100	2000 ms	230660 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; 
}
 
const int N = 3e5 + 10;
 
long long prefix[N];
 
 
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 < long long, int > combine(pair < long long, int > u, pair < long long, 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 < long long, 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 < long long, int > sub(pair < long long, int > u, pair < long long, int > v){
		u.first -= v.first;
		u.second -= v.second;
		return u;
	}
 
	pair < long long, 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 < long long, int > ask(int x, int l, int r){
		if(x < 0) return make_pair(0, 0);
		return query(x, 1, n, l, r);
	}
 
	pair < long long, 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(save[r].second, u, v), ask(save[l - 1].second, u, v));
	}
}treeInside, treeBig, treeSum;
 
vector < int > lst, arr;
  
 
#define getIdx(x) (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(arr.begin(), arr.end(), x) - arr.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];
	other = 2LL * (p - 1 - pos - current.second - smaller.second) * y - (other - current.first - smaller.first); 
	return now + tot + Outside + solve + other;
 
}
 
long long work(int l, int r, int x, int y){
	
	int best = max(mid + 1, x);
	long long ret = Calc(arr[mid], arr[best]);
 
	for(int i = best + 1; i <= y; ++i){
		long long curr = Calc(arr[mid], arr[i]);
		if(curr < ret){
			ret = curr;
			best = i;
		}
	}
 
	if(l != r){
		ret = min(ret, work(l, mid, x, best));
		ret = min(ret, work(mid + 1, r, best, y));
	}
	return ret;
}
 
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() + 10);
	treeBig.Init(lst.size() + 10);
	treeInside.Init(lst.size() + 10);
 
 
	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;
 
  
	return work(0, arr.size(), 1, arr.size()) + 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 Three()':
bridge.cpp:226:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:277:12: warning: unused variable 'ans' [-Wunused-variable]
  long long ans = 1e18;
            ^
bridge.cpp: In function 'int main()':
bridge.cpp:286: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:292: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: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37