oj.uz

Submission #46590

# Submission time Handle Problem Language Result Execution time Memory
46590 2018-04-21T15:29:17 Z aome Palembang Bridges (APIO15_bridge) C++17
22 / 100
 331 ms 35732 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int m, n;
long long res;
long long f[2][N];
pair<int, int> a[N];
vector< pair<int, int> > vec;

struct SegmentTree {
	pair<int, long long> T[4 * 2 * N];

	void init() {
		for (int i = 0; i < 4 * 2 * N; ++i) T[i] = {0, 0};
	}

	#define mid ((l + r) >> 1)

	void upd(int i, int l, int r, int p) {
		if (l == r) {
			T[i] = {1, vec[l].first}; return; 
		}
		if (mid >= p) upd(i << 1, l, mid, p);
		else upd(i << 1 | 1, mid + 1, r, p);
		T[i] = {T[i << 1].first + T[i << 1 | 1].first, T[i << 1].second + T[i << 1 | 1].second};
	}

	int find(int i, int l, int r, int k) {
		if (l == r) return l;
		if (k <= T[i << 1].first) return find(i << 1, l, mid, k);
		return find(i << 1 | 1, mid + 1, r, k - T[i << 1].first);
	}

	long long get(int i, int l, int r, int L, int R) {
		if (L > r || l > R) return 0;
		if (L <= l && r <= R) return T[i].second;
		return get(i << 1, l, mid, L, R) + get(i << 1 | 1, mid + 1, r, L, R);
	}

	#undef mid
} IT;

int main() {
	ios::sync_with_stdio(false);
	cin >> m >> n;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		char x, y;
		++cnt;
		cin >> x >> a[cnt].first >> y >> a[cnt].second;
		if (a[cnt].first > a[cnt].second) {
			swap(a[cnt].first, a[cnt].second);
		}
		if (x == y) res += a[cnt].second - a[cnt].first, cnt--;
	}
	n = cnt;
	sort(a + 1, a + 1 + n, [&] (pair<int, int> x, pair<int, int> y) {
		return x.first + x.second < y.first + y.second;
	});
	for (int i = 1; i <= n; ++i) {
		vec.push_back({a[i].first, i * 2}), vec.push_back({a[i].second, i * 2 + 1});
	}
	sort(vec.begin(), vec.end());
	for (int i = 1; i <= n; ++i) {
		a[i].first = lower_bound(vec.begin(), vec.end(), make_pair(a[i].first, i * 2)) - vec.begin();
		a[i].second = lower_bound(vec.begin(), vec.end(), make_pair(a[i].second, i * 2 + 1)) - vec.begin();
	}
	IT.init();
	for (int i = 1; i <= n; ++i) {
		IT.upd(1, 0, n * 2 - 1, a[i].first);	
		IT.upd(1, 0, n * 2 - 1, a[i].second);
		int p = IT.find(1, 0, n * 2 - 1, i);
		f[0][i] = IT.get(1, 0, n * 2 - 1, p + 1, n * 2 - 1) - IT.get(1, 0, n * 2 - 1, 0, p);
	}
	IT.init();
	for (int i = n; i >= 1; --i) {
		IT.upd(1, 0, n * 2 - 1, a[i].first);	
		IT.upd(1, 0, n * 2 - 1, a[i].second);
		int p = IT.find(1, 0, n * 2 - 1, n - i + 1);
		f[1][i] = IT.get(1, 0, n * 2 - 1, p + 1, n * 2 - 1) - IT.get(1, 0, n * 2 - 1, 0, p);		
	}
	if (m == 1) cout << f[0][n] + res + n;
	else {
		long long mn = 1e18;
		for (int i = 1; i <= n; ++i) mn = min(mn, f[0][i - 1] + f[1][i]);
		cout << mn + res + n;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12920 KB Output is correct
2 Correct 12 ms 12920 KB Output is correct
3 Correct 13 ms 12980 KB Output is correct
4 Correct 13 ms 13244 KB Output is correct
5 Correct 17 ms 13248 KB Output is correct
6 Correct 23 ms 13456 KB Output is correct
7 Correct 13 ms 13456 KB Output is correct
8 Correct 13 ms 13456 KB Output is correct
9 Correct 13 ms 13456 KB Output is correct
10 Correct 13 ms 13456 KB Output is correct
11 Correct 13 ms 13456 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13456 KB Output is correct
2 Correct 11 ms 13456 KB Output is correct
3 Correct 14 ms 13476 KB Output is correct
4 Correct 12 ms 13476 KB Output is correct
5 Correct 14 ms 13524 KB Output is correct
6 Correct 12 ms 13588 KB Output is correct
7 Correct 14 ms 13588 KB Output is correct
8 Correct 12 ms 13588 KB Output is correct
9 Correct 13 ms 13600 KB Output is correct
10 Correct 13 ms 13624 KB Output is correct
11 Correct 13 ms 13644 KB Output is correct
12 Correct 331 ms 18552 KB Output is correct
13 Correct 288 ms 20828 KB Output is correct
14 Correct 233 ms 21612 KB Output is correct
15 Correct 151 ms 21812 KB Output is correct
16 Correct 149 ms 24968 KB Output is correct
17 Correct 174 ms 27400 KB Output is correct
18 Correct 129 ms 29320 KB Output is correct
19 Correct 192 ms 31576 KB Output is correct
20 Correct 179 ms 33480 KB Output is correct
21 Correct 185 ms 35732 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 35732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 35732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 35732 KB Output isn't correct
2 Halted 0 ms 0 KB -