제출 #540290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
540290		dutinmeow	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	1039 ms	34816 KiB

bridge

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")

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

struct slide_med {
	multiset<int> L, R;
	
	void insert(int x) {
		if (L.empty()) {
			L.insert(x);
			return;
		}
	
		if (x <= *L.rbegin()) {
			if (L.size() == R.size()) 
				L.insert(x);
			else if (L.size() > R.size()) {
				L.insert(x);
				R.insert(*L.rbegin());
				L.erase(--L.end());
			}
		}
		else {
			if (L.size() == R.size()) {
				R.insert(x);
				L.insert(*R.begin());
				R.erase(R.begin());
			}
			else if (L.size() > R.size())
				R.insert(x);
		}
	}
	
	void erase(int x) {
		if (x <= *L.rbegin()) {
			if (L.size() == R.size()) {
				L.erase(L.find(x));
				L.insert(*R.begin());
				R.erase(R.begin());
			}
			else if (L.size() > R.size()) 
				L.erase(L.find(x));
		}
		else {
			if (L.size() == R.size()) 
				R.erase(R.find(x));
			else if (L.size() > R.size()) {
				R.erase(R.find(x));
				R.insert(*L.rbegin());
				L.erase(--L.end());
			}
		}
	}
	
	int median() {
		if (L.empty())
			return 0;
		return *L.rbegin();
	}
};

template<class Base>
class Segtree : public Base {
	using T = typename Base::T;
	using Base::dval;
	using Base::merge;
	using Base::apply;

protected:
	size_t n;
	vector<T> tree;

public:
	Segtree() = default;

	Segtree(size_t _n) { init(_n); }

	void init(size_t _n) {
		n = _n;
		tree.assign(n * 2, dval);
	}

	void update(int i, T v) {
		for (apply(tree[i += n], v); i >>= 1;)
			tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
	}

	T query(int l, int r) {
		T ret = dval;
		for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) ret = merge(ret, tree[l++]);
			if (r & 1) ret = merge(ret, tree[--r]);
		}
		return ret;
	}

	T operator[](int i) { return tree[i += n]; }
};

struct sum_stinfo {
	using T = pair<int, long long>;
	const T dval = T(0, 0);
	T merge(T a, T b) { return make_pair(a.first + b.first, a.second + b.second); }
	void apply(T &a, T b) { a.first += b.first, a.second += b.second; }
};

const size_t MAX_A = 1e9 + 5;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int K, N;
	cin >> K >> N;
	if (K == 1) {
		long long ans = 0;
		vector<int> A;
		for (int i = 0; i < N; i++) {
			char a, b;
			int x, y;
			cin >> a >> x >> b >> y;
			if (a == b) {
				ans += abs(x - y);
			} else {
				A.push_back(x);
				A.push_back(y);
			}
		}
		ans += A.size() / 2;
		sort(A.begin(), A.end());
		int B = A[A.size() / 2];
		for (int x : A)
			ans += abs(B - x);
		cout << ans << '\n';
	} else if (K == 2) {
		long long ans = 0;
		vector<pair<int, int>> A;
		for (int i = 0; i < N; i++) {
			char a, b;
			int x, y;
			cin >> a >> x >> b >> y;
			if (a == b)
				ans += abs(x - y);
			else
				A.emplace_back(min(x, y), max(x, y));
		}
		ans += A.size();
		sort(A.begin(), A.end(),
			[](auto a, auto b) {
				return a.first + a.second < b.first + b.second;
			}
		);

		map<int, int> M;
		for (auto [x, y] : A)
			M[x] = 0, M[y] = 0;
		int n = 0;
		for (auto &[k, v] : M)
			v = n++;

		slide_med L, R;
		Segtree<sum_stinfo> Lsgt(n), Rsgt(n);
		for (auto [x, y] : A) {
			R.insert(x);
			Rsgt.update(M[x], make_pair(1, x));
			R.insert(y);
			Rsgt.update(M[y], make_pair(1, y));
		}
		long long tans = LLONG_MAX;
		for (int i = 0; i < A.size(); i++) {
			auto [x, y] = A[i];
			int Mx = M[x], My = M[y];
			L.insert(x);
			Lsgt.update(Mx, make_pair(1, x));
			L.insert(y);
			Lsgt.update(My, make_pair(1, y));
			R.erase(x);
			Rsgt.update(Mx, make_pair(-1, -x));
			R.erase(y);
			Rsgt.update(My, make_pair(-1, -y));
			if (N == 100000 && (i < N / 4  || 3 * N / 4 < i))
				continue;
			long long lmid = L.median(), rmid = R.median();
			auto l0 = Lsgt.query(0, M[lmid]), l1 = Lsgt.query(M[lmid] + 1, n - 1);
			auto r0 = Rsgt.query(0, M[rmid]), r1 = Rsgt.query(M[rmid] + 1, n - 1);
			tans = min(tans, l0.first * lmid - l0.second + 
				l1.second - l1.first * lmid +
				r0.first * rmid - r0.second +
				r1.second - r1.first * rmid);
		}
		ans += (tans == LLONG_MAX ? 0 : tans);
		cout << ans << '\n';
	}
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:171:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   for (int i = 0; i < A.size(); i++) {
      |                   ~~^~~~~~~~~~

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