Submission #455295

#	Time	Username	Problem	Language	Result	Execution time	Memory
455295		nonsensenonsense1	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	79 ms	5300 KiB

bridge

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

struct item {
	long long sum;
	int amt;
	item() {
		sum = amt = 0;
	}
	void operator+=(int k) {
		sum += k;
		++amt;
	}
	void operator-=(int k) {
		sum -= k;
		--amt;
	}
	long long calc(int x) {
		return sum - (long long)x * amt;
	}
};

const int N = 100000;
int n, task;
std::vector<std::pair<int, int> > pt, a, md;
item il, ir, jl, jr;
bool u[N], i_vis[N], j_vis[N], transfer[N];

long long eval(int cur, int jval) 
{
	return ir.calc(cur) - il.calc(cur) + jr.calc(jval) - jl.calc(jval);
}

void move_k(int &k, int cur, int jval) 
{
	while (k < n && md[k].first <= cur + jval) {
		if (u[md[k].second]) {
			jl -= a[md[k].second].second - 1;
			ir += a[md[k].second].first;
			transfer[md[k].second] = true;
		}
		++k;
	}
}

void move_j(int &j, int &k, int cur, int &jval) 
{
	while (j < n << 1 && jl.amt - jr.amt <= 0) {
		jval = pt[j].first;
		do {
			if (!j_vis[pt[j].second]) {
				jr -= jval;
				j_vis[pt[j].second] = true;
			}
			else if (a[pt[j].second].first > cur) {
				u[pt[j].second] = true;
				jl += jval;
			}
			++j;
		} while (j < n << 1 && pt[j].first == jval);
		move_k(k, cur, jval);
	}
}

int main() 
{
	scanf("%d%d", &task, &n);
	long long ans_add = 0;
	for (int i = 0; i < n; ++i) {
		char type1, type2;
		int l, r;
		scanf(" %c%d %c%d", &type1, &l, &type2, &r);
		assert(l >= 0 && r <= 1000000000);
		if (l > r) std::swap(l, r);
		ans_add += r - l;
		if (type1 != type2) {
			++ans_add;
			pt.push_back(std::make_pair(l, (int)a.size()));
			pt.push_back(std::make_pair(r, (int)a.size()));
			md.push_back(std::make_pair(l + r, (int)a.size()));
			a.push_back(std::make_pair(l, r + 1));
		}
	}
	std::sort(pt.begin(), pt.end());
	std::sort(md.begin(), md.end());
	n = (int)a.size();
	for (int i = 0; i < n; ++i) jr += a[i].first;
	int cur = 1 << 31, jval = 1 << 31, j = 0, k = 0;
	move_j(j, k, cur, jval);
	long long ans = eval(cur, jval);
	if (task == 1) {
		printf("%lld\n", ans * 2 + ans_add);
		return 0;
	}
	for (int i = 0; i < n << 1;) {
		cur = pt[i].first;
		move_k(k, cur, jval);
		do {
			if (!i_vis[pt[i].second]) {
				if (u[pt[i].second]) {
					assert(transfer[pt[i].second]);
					u[pt[i].second] = false;
					ir -= pt[i].first;
				}
				i_vis[pt[i].second] = true;
			}
			else il += cur;
			++i;
		} while (i < n << 1 && pt[i].first == cur);
		move_j(j, k, cur, jval);
		assert(i == (n << 1) || i < j);
		assert(eval(cur, jval) >= 0);
		ans = std::min(ans, eval(cur, jval));
	}
	for (int i = 0; i < n; ++i) il -= a[i].second - 1;
	assert(!il.sum && !il.amt && !jl.sum && !jl.amt && !ir.sum && !ir.amt && !jr.sum && !jr.amt);
	printf("%lld\n", ans * 2 + ans_add);
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d", &task, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf(" %c%d %c%d", &type1, &l, &type2, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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