제출 #671186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671186		NothingXD	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	1765 ms	29676 KiB

bridge

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;
const ll inf = 1e18;

int n, k, N, M, L = 1, R, x[maxn], y[maxn], cnt[maxn];
pll seg[maxn << 2];
pll operator + (pll a, pll b){
	pll res;
	res.F = a.F + b.F;
	res.S = a.S + b.S;
	return res;
}

ll dp[maxn], sum[maxn], pre[maxn], suf[maxn], ans, val;
vector<int> num, snum, ql[maxn], qr[maxn];

void add(int v, int l, int r, int idx, pll val){
	if (l + 1 == r){
		seg[v] = seg[v] + val;
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid) add(v << 1, l, mid, idx, val);
	else add(v << 1 | 1, mid, r, idx, val);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

pll get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return {0, 0};
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	return get(v << 1, l, mid, ql, qr)
		+ get(v << 1 | 1, mid, r, ql, qr);
}

ll get(int l, int r){
	while(R < r){
		R++;
		for (auto x: qr[R]){
			if (x < L) continue;
			val -= num[R-1] - num[x-1];
			int ptr = lower_bound(all(snum), num[R-1] + num[x-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {num[R-1] + num[x-1], 1});
		}
	}
	while(l < L){
		L--;
		for (auto x: ql[L]){
			if (x > R) continue;
			val -= num[x-1] - num[L-1];
			int ptr = lower_bound(all(snum), num[x-1] + num[L-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {num[x-1] + num[L-1], 1});
		}
	}
	while(R > r){
		for (auto x: qr[R]){
			if (x < L) continue;
			val += num[R-1] - num[x-1];
			int ptr = lower_bound(all(snum), num[R-1] + num[x-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {-num[R-1] - num[x-1], -1});
		}
		R--;
	}
	while(l > L){
		for (auto x: ql[L]){
			if (x > R) continue;
			val += num[x-1] - num[L-1];
			int ptr = lower_bound(all(snum), num[x-1] + num[L-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {-num[x-1] - num[L-1], -1});
		}
		L++;
	}
	int mid = num[R-1] + num[L-1];
	int ptr = upper_bound(all(snum), mid) - snum.begin() + 1;
	pll tmp = get(1, 1, M+1, 1, ptr);
	ll res = tmp.F - tmp.S * 2 * num[L-1];
	tmp = get(1, 1, M+1, ptr, M+1);
	res += tmp.S * 2 * num[R-1] - tmp.F;
	return res + val;
}

void solve(int l, int r, int ql, int qr){
	if (r < l) return;
	int mid = (l + r) >> 1;
	int ptr = ql;
	dp[mid] = pre[ql] + suf[mid] + get(ql, mid);
	for (int i = ql; i <= mid && i <= qr; i++){
		ll tmp = pre[i] + suf[mid] + get(i, mid);
		if (tmp < dp[mid]){
			dp[mid] = tmp;
			ptr = i;
		}
	}
	solve(l, mid-1, ql, ptr);
	solve(mid+1, r, ptr, qr);
}

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

	cin >> k >> n;

	for (int i = 1; i <= n; i++){
		char s, t; cin >> s >> x[i] >> t >> y[i];
		if (x[i] > y[i]) swap(x[i], y[i]);
		if (s == t){
			ans += y[i] - x[i];
			x[i] = y[i] = -1;
		}
		else{
			ans += y[i] - x[i] + 1;
			num.push_back(x[i]);
			num.push_back(y[i]);
			snum.push_back(x[i] + y[i]);
		}
	}


	if (num.empty()) return cout << ans << '\n', 0;

	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));
	sort(all(snum));
	snum.resize(distance(snum.begin(), unique(all(snum))));
	N = num.size();
	M = snum.size();

	for (int i = 1; i <= n; i++){
		if (x[i] == -1) continue;
		x[i] = lower_bound(all(num), x[i]) - num.begin() + 1;
		y[i] = lower_bound(all(num), y[i]) - num.begin() + 1;
		cnt[y[i]]++;
		sum[y[i]] += 2 * num[y[i]-1];
		ql[x[i]].push_back(y[i]);
		qr[y[i]].push_back(x[i]);
	}

	for (int i = 1; i <= N; i++){
		cnt[i] += cnt[i-1];
		sum[i] += sum[i-1];
		pre[i] = 2ll * cnt[i] * num[i-1] - sum[i];
	}

	memset(cnt, 0, sizeof cnt);
	memset(sum, 0, sizeof sum);

	for (int i = 1; i <= n; i++){
		if (x[i] == -1) continue;
		cnt[x[i]]++;
		sum[x[i]] += 2 * num[x[i] - 1];
	}

	for (int i = N; i; i--){
		cnt[i] += cnt[i+1];
		sum[i] += sum[i+1];
		suf[i] = sum[i] - 2ll * cnt[i] * num[i-1];
	}



	if (k == 1){
		ll res = inf;
		for (int i = 1; i <= N; i++){
			res = min(res, pre[i] + suf[i]);
		}
		cout << ans + res << '\n';
		return 0;
	}

	solve(1, N, 1, N);

	ll res = inf;
	for (int i = 1; i <= N; i++){
		res = min(res, dp[i]);
	}

	cout << ans + res << '\n';

	return 0;
}

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