Submission #455187

#	Time	Username	Problem	Language	Result	Execution time	Memory
455187		nonsensenonsense1	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	71 ms	7212 KiB

bridge

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

struct item {
	long long sum;
	int amt;
	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, k;
std::vector<std::pair<int, int> > pt, a, md;
item il, ir, jl, jr;
bool u[N];

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;
			ir += a[md[k].second].first;
		}
		++k;
	}
}

void move_j(int &j, int cur, int &jval) 
{
	while (j < n << 1 && jl.amt - jr.amt <= 0) {
		jval = pt[j].first;
		do {
			if (jval == a[pt[j].second].first) jr -= jval;
			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);
	}
}

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

int main() 
{
	scanf("%d%d", &k, &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);
		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;
	long long ans = ~((long long)1 << 63);
	int cur = 1 << 31, jval = 1 << 31, j = 0, k = 0;
	move_j(j, cur, jval);
	printf("%lld\n", eval(cur, jval) * 2 + ans_add);
	return 0;
	for (int i = 0; i < n << 1;) {
		cur = pt[i].first;
		move_k(k, cur, jval);
		do {
			if (cur == a[pt[i].second].first) {
				if (u[pt[i].second]) {
					u[pt[i].second] = false;
					ir.sum -= pt[i].first;
				}
			}
			else il += cur;
			++i;
		} while (i < n << 1 && pt[i].first == cur);
		move_j(j, cur, jval);
		ans = std::min(ans, eval(cur, jval));
	}
	return 0;
}

Compilation message (stderr)

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

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