Submission #317874

#	Time	Username	Problem	Language	Result	Execution time	Memory
317874		parsabahrami	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	727 ms	24828 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<pair<pll, ll>> st; vector<ll> compress = {-INF}; vector<pair<pll, 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), [&](pair<pll, ll> x, pair<pll, ll> y) {
		return x.F.F + x.F.S < y.F.F + y.F.S;
	});
	n = sz(vec); if (n == 0) return !printf("%lld\n", sum);
	for (ll i = 1; i <= n; i++) {
		ll l = vec[i - 1].F.F, r = vec[i - 1].F.S, id = vec[i - 1].S;
		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}, 1});
		st.insert({{r, id}, 2});
		ll median = (st.find_by_order((sz(st) + 1) / 2)->F).F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		L[i] = median * st.order_of_key({{median, MOD}, 3}) - get(pm);
		L[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({{median, MOD}, 3}));
	}
	memset(fen, 0, sizeof fen);
	if (k == 1) return !printf("%lld\n", L[n] + sum);
	st.clear();
	for (ll i = n; i; i--) {
		ll l = vec[i - 1].F.F, r = vec[i - 1].F.S, id = vec[i - 1].S;
		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}, 1});
		st.insert({{r, id}, 2});
		ll median = (st.find_by_order((sz(st) + 1) / 2)->F).F;
		ll pm = lower_bound(all(compress), median) - compress.begin();
		R[i] = median * st.order_of_key({{median, MOD}, 3}) - get(pm);
		R[i] += get(MAXN - 1) - get(pm) - median * (sz(st) - st.order_of_key({{median, MOD}, 3}));
	}
	ans = L[1] + R[2];
	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: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37