Submission #48199

#	Time	Username	Problem	Language	Result	Execution time	Memory
48199		Kmcode	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	5 ms	4204 KiB

bridge

#include "bits/stdc++.h"
using namespace std;

int n;
int k;

vector<pair<long long int, long long int> > v;

vector<long long int> vv;

bool cmp(pair<long long int, long long int> a, pair<long long int, long long int> b) {
	return a.first + a.second < b.first + b.second;
}

#define MAX 300002

long long int ans[MAX];

long long int bit[MAX];
int cnt[MAX];

void add(int i, long long int x) {
	i++;
	while (i < MAX) {
		bit[i] += x;
		cnt[i]++;
		i += i&-i;
	}
}
long long int sum(int i) {
	long long int r = 0;
	i++;
	while (i) {
		r += bit[i];
		i -= i&-i;
	}
	return r;
}
long long int rng(int l, int r) {
	long long int ret = sum(r);
	if (l)ret -= sum(l - 1);
	return ret;
}

int get_id(long long int val) {
	return lower_bound(vv.begin(), vv.end(),val) - vv.begin();
}

long long int sum_cnt(int idx) {
	int r = 0;
	idx++;
	while (idx) {
		r += cnt[idx];
		idx -= idx&-idx;
	}
	return r;
}

long long int rng_cnt(int l, int r) {
	int ret = sum_cnt(r);
	if (l)ret -= sum_cnt(l - 1);
	return ret;
}

long long int tmp[MAX];

int main() {
	cin >> k >> n;
	long long int ans = 0;
	for (int i = 0; i < n; i++) {
		long long int a, b,aa,bb;
		char A[2], B[2];
		scanf("%s%lld%s%lld", A, &aa, B, &bb);
		if (A[0] == B[0]) {
			ans += abs(aa-bb);
		}
		else {
			ans++;
			tie(a, b) = minmax(aa, bb);
			v.push_back(make_pair(a, b));
			vv.push_back(a);
			vv.push_back(b);
		}
	}
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	sort(v.begin(), v.end(), cmp);
	long long int AA = LLONG_MAX;
	{
		int idx = 0;
		int cn = 0;
		for (int i = 0; i < v.size(); i++) {
			while (idx <= i) {
				add(get_id(v[idx].first), v[idx].first);
				add(get_id(v[idx].second), v[idx].second);
				cn++;
				idx++;
			}
			int mint = 0;
			int maxt = vv.size() - 1;
			while (mint + 1 < maxt) {
				int mid = (mint + maxt) >> 1;
				if (sum_cnt(mid) >= cn) {
					maxt = mid;
				}
				else {
					mint = mid;
				}
			}
			if (sum_cnt(mint) >= cn) {
				maxt = mint;
			}
			else{
				mint = maxt;
			}
			long long int sm =rng_cnt(0, mint)*vv[mint] - rng(0, mint);
			sm += rng(mint + 1, vv.size() - 1) - rng_cnt(mint+1,vv.size()-1)*vv[mint];
			tmp[i]=sm;
		}
		AA = min(AA, tmp[vv.size() - 1]);
	}
	{
		long long int las = -11111111;
		memset(cnt, 0, sizeof(cnt));
		memset(bit, 0, sizeof(bit));
		int idx = v.size()-1;
		int cn = 0;
		for (int i = vv.size()-1; i>=0; i--) {
			while (idx >=i) {
				add(get_id(v[idx].first), v[idx].first);
				add(get_id(v[idx].second), v[idx].second);
				cn++;
				idx--;
			}
			int mint = 0;
			int maxt = vv.size() - 1;
			while (mint + 1 < maxt) {
				int mid = (mint + maxt) >> 1;
				if (sum_cnt(mid) >= cn) {
					maxt = mid;
				}
				else {
					mint = mid;
				}
			}
			if (sum_cnt(mint) >= cn) {
				maxt = mint;
			}
			else {
				mint = maxt;
			}
			long long int sm = rng_cnt(0, mint)*vv[mint] - rng(0, mint);
			sm += rng(mint + 1, vv.size() - 1) - rng_cnt(mint + 1, vv.size() - 1)*vv[mint];
			if (i)sm += tmp[i - 1];
			AA = min(AA, sm);
			las = sm;
		}
		if (k == 1)AA = las;
		ans += AA;
	}
	if (k == 1) {
		printf("%lld\n", ans - AA + tmp[vv.size()-1]);
		return 0;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < v.size(); i++) {
                   ~~^~~~~~~~~~
bridge.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%lld%s%lld", A, &aa, B, &bb);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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