oj.uz

Submission #369812

# Submission time Handle Problem Language Result Execution time Memory
369812 2021-02-22T13:13:40 Z pavement Palembang Bridges (APIO15_bridge) C++17
100 / 100
 878 ms 60808 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#ifdef WIN_32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int K, N, tmpans = LLONG_MAX, ans, idx, _cnt, I[100005], S[100005], T[100005], leftval[100005], ft[200005], ft2[200005];
char P, Q;
vector<int> vec;

inline int ls(int x) { return x & -x; }

void upd(int p, int v) {
	for (; p <= 2 * N; p += ls(p)) ft[p] += v, ft2[p]++;
}

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

int cnt(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft2[p];
	return r;
}

struct slope {
	ordered_set ch;
	int m;
	slope(int _m) : m(_m) {}
};

int disc(int x) {
	return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> K >> N;
	for (int i = 1; i <= N; i++) {
		cin >> P >> S[i] >> Q >> T[i];
		S[i]++;
		T[i]++;
		if (P == Q) {
			ans += llabs(S[i] - T[i]);
			continue;
		}
		if (S[i] > T[i]) swap(S[i], T[i]);
		I[++idx] = i;
	}
	N = idx;
	sort(I + 1, I + 1 + N, [](const auto &a, const auto &b) {
		return S[a] + T[a] < S[b] + T[b];
	});
	ans += idx;
	for (int i = 1; i <= N; i++) vec.pb(S[I[i]]), vec.pb(T[I[i]]);
	sort(vec.begin(), vec.end());
	slope *run = new slope(0);
	for (int i = 1; i <= N; i++) {
		upd(disc(T[I[i]]), T[I[i]]);
		upd(disc(S[I[i]]), S[I[i]]);
		run->ch.insert(mp(T[I[i]], ++_cnt));
		run->ch.insert(mp(T[I[i]], ++_cnt));
		run->ch.insert(mp(S[I[i]], ++_cnt));
		run->ch.insert(mp(S[I[i]], ++_cnt));
		run->m += 2;
		int val = run->ch.find_by_order(run->ch.size() - run->m)->first, curr = 0;
		curr = (qry(2 * N) - qry(disc(val) - 1)) - val * (cnt(2 * N) - cnt(disc(val) - 1));
		curr += cnt(disc(val) - 1) * val - qry(disc(val) - 1);
		leftval[i] = curr;
	}
	if (K == 1) return cout << leftval[N] + ans << '\n', 0;
	memset(ft, 0, sizeof ft);
	memset(ft2, 0, sizeof ft2);
	tmpans = leftval[N];
	run = new slope(0);
	for (int i = N; i >= 1; i--) {
		upd(disc(T[I[i]]), T[I[i]]);
		upd(disc(S[I[i]]), S[I[i]]);
		run->ch.insert(mp(T[I[i]], ++_cnt));
		run->ch.insert(mp(T[I[i]], ++_cnt));
		run->ch.insert(mp(S[I[i]], ++_cnt));
		run->ch.insert(mp(S[I[i]], ++_cnt));
		run->m += 2;
		int val = run->ch.find_by_order(run->ch.size() - run->m)->first, curr = 0;
		curr = (qry(2 * N) - qry(disc(val) - 1)) - val * (cnt(2 * N) - cnt(disc(val) - 1));
		curr += cnt(disc(val) - 1) * val - qry(disc(val) - 1);
		tmpans = min(tmpans, leftval[i - 1] + curr);
	}
	cout << ans + tmpans << '\n';
}

Compilation message

bridge.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main() {
      |      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 382 ms 31100 KB Output is correct
13 Correct 467 ms 35556 KB Output is correct
14 Correct 442 ms 31204 KB Output is correct
15 Correct 239 ms 21224 KB Output is correct
16 Correct 401 ms 31972 KB Output is correct
17 Correct 347 ms 35556 KB Output is correct
18 Correct 212 ms 35300 KB Output is correct
19 Correct 238 ms 35684 KB Output is correct
20 Correct 387 ms 32228 KB Output is correct
21 Correct 385 ms 35328 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3564 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 2 ms 3564 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 2 ms 3564 KB Output is correct
8 Correct 2 ms 3564 KB Output is correct
9 Correct 3 ms 3564 KB Output is correct
10 Correct 2 ms 3564 KB Output is correct
11 Correct 2 ms 3564 KB Output is correct
12 Correct 2 ms 3564 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 2 ms 3564 KB Output is correct
4 Correct 2 ms 3564 KB Output is correct
5 Correct 2 ms 3564 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 3 ms 3692 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 3 ms 3564 KB Output is correct
10 Correct 3 ms 3564 KB Output is correct
11 Correct 2 ms 3564 KB Output is correct
12 Correct 2 ms 3564 KB Output is correct
13 Correct 5 ms 4076 KB Output is correct
14 Correct 5 ms 4076 KB Output is correct
15 Correct 5 ms 4076 KB Output is correct
16 Correct 3 ms 3692 KB Output is correct
17 Correct 4 ms 3820 KB Output is correct
18 Correct 3 ms 3692 KB Output is correct
19 Correct 5 ms 4076 KB Output is correct
20 Correct 6 ms 4076 KB Output is correct
21 Correct 5 ms 4076 KB Output is correct
22 Correct 5 ms 4076 KB Output is correct
23 Correct 5 ms 4076 KB Output is correct
24 Correct 6 ms 4076 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 2 ms 3564 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 2 ms 3564 KB Output is correct
6 Correct 2 ms 3436 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 3 ms 3584 KB Output is correct
10 Correct 2 ms 3564 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 3 ms 3564 KB Output is correct
13 Correct 5 ms 4076 KB Output is correct
14 Correct 5 ms 4076 KB Output is correct
15 Correct 5 ms 4076 KB Output is correct
16 Correct 3 ms 3692 KB Output is correct
17 Correct 4 ms 3820 KB Output is correct
18 Correct 3 ms 3692 KB Output is correct
19 Correct 6 ms 4076 KB Output is correct
20 Correct 5 ms 4076 KB Output is correct
21 Correct 5 ms 4076 KB Output is correct
22 Correct 5 ms 4076 KB Output is correct
23 Correct 5 ms 4076 KB Output is correct
24 Correct 6 ms 4076 KB Output is correct
25 Correct 722 ms 59124 KB Output is correct
26 Correct 653 ms 59256 KB Output is correct
27 Correct 867 ms 60132 KB Output is correct
28 Correct 878 ms 60696 KB Output is correct
29 Correct 865 ms 60772 KB Output is correct
30 Correct 382 ms 33768 KB Output is correct
31 Correct 832 ms 60004 KB Output is correct
32 Correct 668 ms 60772 KB Output is correct
33 Correct 387 ms 60260 KB Output is correct
34 Correct 444 ms 60808 KB Output is correct
35 Correct 752 ms 60140 KB Output is correct
36 Correct 806 ms 60388 KB Output is correct
37 Correct 830 ms 59108 KB Output is correct