Submission #317870

#	Time	Username	Problem	Language	Result	Execution time	Memory
317870		parsabahrami	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	3 ms	2048 KiB

bridge

//! God Is Dead
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define sonic(x)  					sort(all(x)); x.resize(unique(all(x)) - (x).begin());

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 2e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll n, k, fen[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN], sum = 0, ans = 0;
Tree<pll> st; vector<ll> compress = {-INF}; vector<tuple<ll, ll, ll>> vec;

void update(ll id, ll x) {
	for (; id < MAXN; id += id & -id) {
		fen[id] += x;
	}
}

ll get(ll pos, ll res = 0) {
	for (; pos; pos -= pos & -pos) {
		res += fen[pos];
	}
	return res;
}

int main() {
	scanf("%lld%lld", &k, &n);
	for (ll i = 1; i <= n; i++) {
		char s[2]; scanf("%s%lld%s%lld", s, &A[i], s + 1, &B[i]);
		if (s[0] == s[1]) sum += abs(A[i] - B[i]);
		else {
			sum++;
			vec.push_back({A[i], B[i], i}); compress.push_back(A[i]);
			compress.push_back(B[i]);
		}
	}
	sonic(compress);
	sort(all(vec), [&](auto x, auto y) {
		return get<0>(x) + get<1>(x) < get<0>(y) + get<1>(y);
	});
	n = sz(vec); if (n == 0) return !printf("%lld\n", sum);
	for (ll i = 1; i <= n; i++) {
		auto[l, r, id] = vec[i - 1];
		ll pl = lower_bound(all(compress), l) - compress.begin();
		ll pr = lower_bound(all(compress), r) - compress.begin();
		update(pl, l);
		update(pr, r);
		st.insert({l, id});
		st.insert({r, id});
		ll median = st.find_by_order((sz(st) + 1) / 2)->F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		L[i] = median * st.order_of_key({median, MOD}) - get(pm);
		L[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({median, MOD}));
	}
	memset(fen, 0, sizeof fen);
	if (k == 1) return !printf("%lld\n", L[n] + sum);
	st.clear();
	for (ll i = n; i; i--) {
		auto[l, r, id] = vec[i - 1];
		ll pl = lower_bound(all(compress), l) - compress.begin();
		ll pr = lower_bound(all(compress), r) - compress.begin();
		update(pl, l);
		update(pr, r);
		st.insert({l, id});
		st.insert({r, id});
		ll median = st.find_by_order((sz(st) + 1) / 2)->F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		R[i] = median * st.order_of_key({median, MOD}) - get(pm);
		R[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({median, MOD}));
	}
	ans = L[n];
	for (ll i = 1; i < n; i++)  {
		ans = min(ans, L[i] + R[i + 1]);
	}
	printf("%lld\n", ans + sum);
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%lld%lld", &k, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
bridge.cpp:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   char s[2]; scanf("%s%lld%s%lld", s, &A[i], s + 1, &B[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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