답안 #46591 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46591	2018-04-21T15:46:46 Z	aome	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	341 ms	40240 KB

bridge

#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 = 0; i <= n; ++i) mn = min(mn, f[0][i] + f[1][i + 1]);
		cout << mn + res + n;
	}
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	12920 KB	Output is correct
2	Correct	12 ms	12920 KB	Output is correct
3	Correct	13 ms	12972 KB	Output is correct
4	Correct	13 ms	12972 KB	Output is correct
5	Correct	13 ms	12972 KB	Output is correct
6	Correct	13 ms	12972 KB	Output is correct
7	Correct	16 ms	13024 KB	Output is correct
8	Correct	13 ms	13072 KB	Output is correct
9	Correct	13 ms	13208 KB	Output is correct
10	Correct	13 ms	13208 KB	Output is correct
11	Correct	12 ms	13208 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	13208 KB	Output is correct
2	Correct	11 ms	13208 KB	Output is correct
3	Correct	13 ms	13208 KB	Output is correct
4	Correct	14 ms	13260 KB	Output is correct
5	Correct	13 ms	13260 KB	Output is correct
6	Correct	13 ms	13260 KB	Output is correct
7	Correct	12 ms	13260 KB	Output is correct
8	Correct	17 ms	13260 KB	Output is correct
9	Correct	13 ms	13260 KB	Output is correct
10	Correct	16 ms	13260 KB	Output is correct
11	Correct	13 ms	13260 KB	Output is correct
12	Correct	174 ms	17108 KB	Output is correct
13	Correct	341 ms	17236 KB	Output is correct
14	Correct	291 ms	17236 KB	Output is correct
15	Correct	155 ms	17236 KB	Output is correct
16	Correct	149 ms	17236 KB	Output is correct
17	Correct	178 ms	17240 KB	Output is correct
18	Correct	133 ms	17240 KB	Output is correct
19	Correct	181 ms	17240 KB	Output is correct
20	Correct	178 ms	17240 KB	Output is correct
21	Correct	183 ms	17240 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	17240 KB	Output is correct
2	Correct	14 ms	17240 KB	Output is correct
3	Correct	12 ms	17240 KB	Output is correct
4	Correct	12 ms	17240 KB	Output is correct
5	Correct	12 ms	17240 KB	Output is correct
6	Correct	12 ms	17240 KB	Output is correct
7	Correct	11 ms	17240 KB	Output is correct
8	Correct	12 ms	17240 KB	Output is correct
9	Correct	11 ms	17240 KB	Output is correct
10	Correct	12 ms	17240 KB	Output is correct
11	Correct	12 ms	17240 KB	Output is correct
12	Correct	14 ms	17240 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	17240 KB	Output is correct
2	Correct	12 ms	17240 KB	Output is correct
3	Correct	12 ms	17240 KB	Output is correct
4	Correct	12 ms	17240 KB	Output is correct
5	Correct	11 ms	17240 KB	Output is correct
6	Correct	12 ms	17240 KB	Output is correct
7	Correct	14 ms	17240 KB	Output is correct
8	Correct	12 ms	17240 KB	Output is correct
9	Correct	12 ms	17240 KB	Output is correct
10	Correct	15 ms	17240 KB	Output is correct
11	Correct	12 ms	17240 KB	Output is correct
12	Correct	12 ms	17240 KB	Output is correct
13	Correct	13 ms	17240 KB	Output is correct
14	Correct	14 ms	17240 KB	Output is correct
15	Correct	13 ms	17240 KB	Output is correct
16	Correct	13 ms	17240 KB	Output is correct
17	Correct	12 ms	17240 KB	Output is correct
18	Correct	15 ms	17240 KB	Output is correct
19	Correct	13 ms	17240 KB	Output is correct
20	Correct	14 ms	17240 KB	Output is correct
21	Correct	13 ms	17240 KB	Output is correct
22	Correct	14 ms	17240 KB	Output is correct
23	Correct	13 ms	17240 KB	Output is correct
24	Correct	13 ms	17240 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	17240 KB	Output is correct
2	Correct	12 ms	17240 KB	Output is correct
3	Correct	12 ms	17240 KB	Output is correct
4	Correct	12 ms	17240 KB	Output is correct
5	Correct	14 ms	17240 KB	Output is correct
6	Correct	11 ms	17240 KB	Output is correct
7	Correct	11 ms	17240 KB	Output is correct
8	Correct	11 ms	17240 KB	Output is correct
9	Correct	11 ms	17240 KB	Output is correct
10	Correct	12 ms	17240 KB	Output is correct
11	Correct	12 ms	17240 KB	Output is correct
12	Correct	12 ms	17240 KB	Output is correct
13	Correct	13 ms	17240 KB	Output is correct
14	Correct	13 ms	17240 KB	Output is correct
15	Correct	14 ms	17240 KB	Output is correct
16	Correct	14 ms	17240 KB	Output is correct
17	Correct	12 ms	17240 KB	Output is correct
18	Correct	12 ms	17240 KB	Output is correct
19	Correct	13 ms	17240 KB	Output is correct
20	Correct	13 ms	17240 KB	Output is correct
21	Correct	13 ms	17240 KB	Output is correct
22	Correct	13 ms	17240 KB	Output is correct
23	Correct	13 ms	17240 KB	Output is correct
24	Correct	14 ms	17240 KB	Output is correct
25	Correct	265 ms	18696 KB	Output is correct
26	Correct	242 ms	19772 KB	Output is correct
27	Correct	266 ms	21424 KB	Output is correct
28	Correct	272 ms	23760 KB	Output is correct
29	Correct	285 ms	26148 KB	Output is correct
30	Correct	145 ms	26148 KB	Output is correct
31	Correct	221 ms	28976 KB	Output is correct
32	Correct	271 ms	31304 KB	Output is correct
33	Correct	138 ms	33132 KB	Output is correct
34	Correct	215 ms	35548 KB	Output is correct
35	Correct	199 ms	37548 KB	Output is correct
36	Correct	198 ms	39620 KB	Output is correct
37	Correct	169 ms	40240 KB	Output is correct

답안 #46591

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 14.0 / 14.0

Subtask #3 9.0 / 9.0

Subtask #4 32.0 / 32.0

Subtask #5 37.0 / 37.0

Subtask #1
8.0 / 8.0

Subtask #2
14.0 / 14.0

Subtask #3
9.0 / 9.0

Subtask #4
32.0 / 32.0

Subtask #5
37.0 / 37.0