oj.uz

Submission #671186

# Submission time Handle Problem Language Result Execution time Memory
671186 2022-12-12T10:12:02 Z NothingXD Palembang Bridges (APIO15_bridge) C++17
100 / 100
 1765 ms 29676 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 > 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 7 ms 12040 KB Output is correct
4 Correct 8 ms 12176 KB Output is correct
5 Correct 10 ms 12116 KB Output is correct
6 Correct 8 ms 12072 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 9 ms 12116 KB Output is correct
10 Correct 7 ms 12040 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9612 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 8 ms 12032 KB Output is correct
4 Correct 7 ms 12224 KB Output is correct
5 Correct 7 ms 12168 KB Output is correct
6 Correct 7 ms 12052 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 7 ms 12168 KB Output is correct
9 Correct 7 ms 12192 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 10 ms 12168 KB Output is correct
12 Correct 36 ms 15928 KB Output is correct
13 Correct 148 ms 23692 KB Output is correct
14 Correct 68 ms 15840 KB Output is correct
15 Correct 78 ms 19056 KB Output is correct
16 Correct 40 ms 16000 KB Output is correct
17 Correct 61 ms 23724 KB Output is correct
18 Correct 74 ms 23904 KB Output is correct
19 Correct 123 ms 23612 KB Output is correct
20 Correct 42 ms 15964 KB Output is correct
21 Correct 80 ms 23824 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 7 ms 12036 KB Output is correct
4 Correct 6 ms 12032 KB Output is correct
5 Correct 9 ms 12060 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 9 ms 12020 KB Output is correct
8 Correct 7 ms 12032 KB Output is correct
9 Correct 7 ms 12088 KB Output is correct
10 Correct 7 ms 12036 KB Output is correct
11 Correct 7 ms 12104 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9692 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12032 KB Output is correct
6 Correct 6 ms 12032 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12088 KB Output is correct
11 Correct 14 ms 12028 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 6 ms 12116 KB Output is correct
14 Correct 8 ms 12116 KB Output is correct
15 Correct 13 ms 12176 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 7 ms 12116 KB Output is correct
18 Correct 8 ms 12160 KB Output is correct
19 Correct 7 ms 12072 KB Output is correct
20 Correct 14 ms 12168 KB Output is correct
21 Correct 8 ms 12244 KB Output is correct
22 Correct 13 ms 12244 KB Output is correct
23 Correct 7 ms 12116 KB Output is correct
24 Correct 13 ms 12244 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9732 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12028 KB Output is correct
5 Correct 8 ms 12036 KB Output is correct
6 Correct 6 ms 12036 KB Output is correct
7 Correct 6 ms 12056 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12012 KB Output is correct
12 Correct 7 ms 12024 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 8 ms 12148 KB Output is correct
15 Correct 13 ms 12276 KB Output is correct
16 Correct 6 ms 12108 KB Output is correct
17 Correct 7 ms 12036 KB Output is correct
18 Correct 8 ms 12164 KB Output is correct
19 Correct 7 ms 12056 KB Output is correct
20 Correct 14 ms 12168 KB Output is correct
21 Correct 8 ms 12176 KB Output is correct
22 Correct 13 ms 12168 KB Output is correct
23 Correct 7 ms 12172 KB Output is correct
24 Correct 14 ms 12288 KB Output is correct
25 Correct 34 ms 16324 KB Output is correct
26 Correct 113 ms 15812 KB Output is correct
27 Correct 1628 ms 28812 KB Output is correct
28 Correct 1765 ms 29620 KB Output is correct
29 Correct 1756 ms 29676 KB Output is correct
30 Correct 779 ms 21788 KB Output is correct
31 Correct 36 ms 16068 KB Output is correct
32 Correct 1576 ms 29548 KB Output is correct
33 Correct 124 ms 25512 KB Output is correct
34 Correct 1725 ms 29412 KB Output is correct
35 Correct 42 ms 15988 KB Output is correct
36 Correct 1573 ms 29656 KB Output is correct
37 Correct 44 ms 16068 KB Output is correct