제출 #33647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33647		sinhriv	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	16 ms	148948 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 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(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];
	//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() + 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;


int cnt = 0;


	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);
		}
	}*/

	for(int i = 1; i <= n; ++i){
		a.emplace_back(rand() % 5000, rand() % 5000);
	}


	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;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'long long int Three()':
bridge.cpp:254:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:311:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < arr.size(); ++i){
                   ^
bridge.cpp:312:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < arr.size(); ++j){
                        ^
bridge.cpp:308:5: warning: unused variable 'cnt' [-Wunused-variable]
 int cnt = 0;
     ^
bridge.cpp: In function 'int main()':
bridge.cpp:323: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:329:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^

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