oj.uz

답안 #671173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671173 2022-12-12T09:21:14 Z NothingXD Palembang Bridges (APIO15_bridge) C++14
22 / 100
 136 ms 25640 KB 
#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 > L) continue;
			val -= num[x] - num[L-1];
			int ptr = lower_bound(all(snum), num[x] + num[L-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {num[x] + 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 > L) continue;
			val += num[x] - num[L-1];
			int ptr = lower_bound(all(snum), num[x] + num[L-1]) - snum.begin() + 1;
			add(1, 1, M+1, ptr, {-num[x] - 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 <= ptr; 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(2, N, 1, N);

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

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

	return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12072 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 9 ms 12168 KB Output is correct
10 Correct 7 ms 12040 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 8 ms 12044 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 8 ms 12204 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12116 KB Output is correct
8 Correct 7 ms 12168 KB Output is correct
9 Correct 7 ms 12196 KB Output is correct
10 Correct 9 ms 12112 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 33 ms 16248 KB Output is correct
13 Correct 136 ms 25640 KB Output is correct
14 Correct 71 ms 16636 KB Output is correct
15 Correct 68 ms 20112 KB Output is correct
16 Correct 36 ms 17216 KB Output is correct
17 Correct 59 ms 25636 KB Output is correct
18 Correct 60 ms 25332 KB Output is correct
19 Correct 131 ms 25624 KB Output is correct
20 Correct 40 ms 17408 KB Output is correct
21 Correct 91 ms 25412 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 12112 KB Output is correct
4 Incorrect 7 ms 12116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 6 ms 12116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9724 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 8 ms 12020 KB Output is correct
4 Incorrect 8 ms 12020 KB Output isn't correct
5 Halted 0 ms 0 KB -