oj.uz

Submission #213545

# Submission time Handle Problem Language Result Execution time Memory
213545 2020-03-26T05:38:27 Z spdskatr Palembang Bridges (APIO15_bridge) C++14
100 / 100
 1724 ms 247664 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <utility>
#include <cstring>
#include <vector>
#include <cassert>
#define MAX (1000000002)
#define fi first
#define se second

using namespace std;
typedef pair<int, int> pii;

int K, N, lv[100005], rv[100005]; 
long long tot, ans;

// Segtree and set data structure that maintains median
class DS {
public:
	set<pii> s1, s2;
	long long st[10000005], lazy[10000005];
	int lc[10000005], rc[10000005], cnt = 2;
	void reset() {
		memset(st, 0, sizeof(st));
		memset(lazy, 0, sizeof(lazy));
		memset(lc, 0, sizeof(lc));
		memset(rc, 0, sizeof(rc));
		s1.clear();
		s2.clear();
		cnt = 2;
	}
	void lu(int lo, int hi, int ind) {
		if (lazy[ind] == 0) return;
		st[ind] += (hi - lo) * lazy[ind];
		if (lo + 1 < hi) {
			if (lc[ind] == 0) lc[ind] = cnt++;
			if (rc[ind] == 0) rc[ind] = cnt++;
			lazy[lc[ind]] += lazy[ind];
			lazy[rc[ind]] += lazy[ind];
		}
		lazy[ind] = 0;
	}
	long long seg_sum(int lo, int hi, int x, int ind) {
		if (ind == 0) return 0;
		lu(lo, hi, ind);
		if (hi <= x+1) {
			return st[ind];
		}
		int mid = (lo + hi) / 2;
		long long res = 0;
		res += seg_sum(lo, mid, x, lc[ind]);
		if (mid <= x) res += seg_sum(mid, hi, x, rc[ind]);
		return res;
	}
	void seg_inc(int lo, int hi, int l, int r, long long val, int ind) {
		lu(lo, hi, ind);
		if (lo >= l && hi <= r) {
			lazy[ind] += val;
			lu(lo, hi, ind);
			return;
		}
		int mid = (lo + hi) / 2;
		if (mid > l) {
			if (lc[ind] == 0) lc[ind] = cnt++;
			seg_inc(lo, mid, l, r, val, lc[ind]);
		}
		if (mid < r) {
			if (rc[ind] == 0) rc[ind] = cnt++;
			seg_inc(mid, hi, l, r, val, rc[ind]);
		}
		lu(lo, mid, lc[ind]);
		lu(mid, hi, rc[ind]);
		st[ind] = st[lc[ind]] + st[rc[ind]];
	}
	void ins(pii p) {
		if (s2.size() == 0 || s2.begin()->fi < p.fi) s2.insert(p);
		else s1.insert(p);
	}
	void bal() {
		while (s2.size() > s1.size() + 1) {
			auto it = s2.begin();
			s1.insert(*it);
			s2.erase(it);
		}
		while (s1.size() > s2.size()) {
			auto it = s1.rbegin();
			s2.insert(*it);
			s1.erase(*it);
		}
	}
	void add_point(int l, int r, int i) {
		seg_inc(0, MAX, r+1, MAX, 2, 1);
		if (l > 0) seg_inc(0, MAX, 1, l+1, -2, 1);
		seg_inc(0, MAX, 0, 1, l * 2, 1);
		ins({ l, 2*i });
		ins({ r, 2*i+1 });
		bal();
	}
	long long query() {
		int pos = s2.begin()->fi;
		return seg_sum(0, MAX, pos, 1);
	}
} med;
vector<pii> sw;

long long pref[100005], suff[100005];

int main() {
	scanf("%d %d", &K, &N);
	for (int i = 0; i < N; i++) {
		char x, y;
		int v1, v2;
		scanf(" %c %d %c %d", &x, &v1, &y, &v2);
		lv[i] = min(v1, v2);
		rv[i] = max(v1, v2);
		if (x != y) {
			sw.push_back({ rv[i] + lv[i], i });
			tot = (tot + rv[i] - lv[i] + 1);
		} else {
			tot = (tot + rv[i] - lv[i]);
		}
	}
	sort(sw.begin(), sw.end());
	int M = sw.size();
	for (int i = 0; i < M; i++) {
		int l = lv[sw[i].se], r = rv[sw[i].se];
		med.add_point(l, r, i);
		pref[i+1] = med.query();
	}
	med.reset();
	for (int i = M-1; i >= 0; i--) {
		int l = lv[sw[i].se], r = rv[sw[i].se];
		med.add_point(l, r, i);
		suff[i+1] = med.query();
	}
	ans = 696969696969696969;
	if (K == 1) {
		ans = pref[M];
	} else {
		for (int i = 0; i <= M; i++) {
			ans = min(ans, pref[i] + suff[i+1]);
		}
	}
	printf("%lld\n", ans + tot);
	return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &K, &N);
  ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %c %d", &x, &v1, &y, &v2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 235128 KB Output is correct
2 Correct 111 ms 235128 KB Output is correct
3 Correct 112 ms 235256 KB Output is correct
4 Correct 118 ms 235256 KB Output is correct
5 Correct 121 ms 235256 KB Output is correct
6 Correct 111 ms 235256 KB Output is correct
7 Correct 118 ms 235256 KB Output is correct
8 Correct 114 ms 235256 KB Output is correct
9 Correct 119 ms 235256 KB Output is correct
10 Correct 114 ms 235256 KB Output is correct
11 Correct 116 ms 235128 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 235128 KB Output is correct
2 Correct 112 ms 235128 KB Output is correct
3 Correct 113 ms 235256 KB Output is correct
4 Correct 117 ms 235256 KB Output is correct
5 Correct 119 ms 235256 KB Output is correct
6 Correct 113 ms 235256 KB Output is correct
7 Correct 118 ms 235256 KB Output is correct
8 Correct 113 ms 235256 KB Output is correct
9 Correct 119 ms 235256 KB Output is correct
10 Correct 113 ms 235256 KB Output is correct
11 Correct 117 ms 235256 KB Output is correct
12 Correct 522 ms 247660 KB Output is correct
13 Correct 1692 ms 247660 KB Output is correct
14 Correct 761 ms 246376 KB Output is correct
15 Correct 965 ms 242544 KB Output is correct
16 Correct 455 ms 247656 KB Output is correct
17 Correct 948 ms 247664 KB Output is correct
18 Correct 600 ms 247656 KB Output is correct
19 Correct 921 ms 247656 KB Output is correct
20 Correct 575 ms 247660 KB Output is correct
21 Correct 740 ms 247656 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235128 KB Output is correct
2 Correct 111 ms 235128 KB Output is correct
3 Correct 113 ms 235128 KB Output is correct
4 Correct 113 ms 235256 KB Output is correct
5 Correct 110 ms 235128 KB Output is correct
6 Correct 111 ms 235128 KB Output is correct
7 Correct 111 ms 235256 KB Output is correct
8 Correct 111 ms 235128 KB Output is correct
9 Correct 113 ms 235128 KB Output is correct
10 Correct 113 ms 235256 KB Output is correct
11 Correct 111 ms 235256 KB Output is correct
12 Correct 111 ms 235256 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 235128 KB Output is correct
2 Correct 112 ms 235128 KB Output is correct
3 Correct 111 ms 235128 KB Output is correct
4 Correct 110 ms 235256 KB Output is correct
5 Correct 111 ms 235128 KB Output is correct
6 Correct 115 ms 235128 KB Output is correct
7 Correct 111 ms 235128 KB Output is correct
8 Correct 112 ms 235128 KB Output is correct
9 Correct 110 ms 235256 KB Output is correct
10 Correct 112 ms 235128 KB Output is correct
11 Correct 111 ms 235128 KB Output is correct
12 Correct 114 ms 235128 KB Output is correct
13 Correct 113 ms 235256 KB Output is correct
14 Correct 114 ms 235256 KB Output is correct
15 Correct 119 ms 235256 KB Output is correct
16 Correct 113 ms 235256 KB Output is correct
17 Correct 114 ms 235256 KB Output is correct
18 Correct 114 ms 235256 KB Output is correct
19 Correct 113 ms 235260 KB Output is correct
20 Correct 121 ms 235256 KB Output is correct
21 Correct 115 ms 235256 KB Output is correct
22 Correct 118 ms 235304 KB Output is correct
23 Correct 112 ms 235256 KB Output is correct
24 Correct 116 ms 235260 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235128 KB Output is correct
2 Correct 112 ms 235128 KB Output is correct
3 Correct 112 ms 235128 KB Output is correct
4 Correct 111 ms 235128 KB Output is correct
5 Correct 109 ms 235128 KB Output is correct
6 Correct 110 ms 235128 KB Output is correct
7 Correct 110 ms 235256 KB Output is correct
8 Correct 110 ms 235256 KB Output is correct
9 Correct 111 ms 235256 KB Output is correct
10 Correct 112 ms 235128 KB Output is correct
11 Correct 109 ms 235128 KB Output is correct
12 Correct 114 ms 235128 KB Output is correct
13 Correct 111 ms 235260 KB Output is correct
14 Correct 111 ms 235256 KB Output is correct
15 Correct 117 ms 235256 KB Output is correct
16 Correct 113 ms 235256 KB Output is correct
17 Correct 112 ms 235256 KB Output is correct
18 Correct 114 ms 235256 KB Output is correct
19 Correct 118 ms 235256 KB Output is correct
20 Correct 118 ms 235256 KB Output is correct
21 Correct 120 ms 235256 KB Output is correct
22 Correct 118 ms 235256 KB Output is correct
23 Correct 116 ms 235256 KB Output is correct
24 Correct 120 ms 235256 KB Output is correct
25 Correct 537 ms 247660 KB Output is correct
26 Correct 680 ms 247656 KB Output is correct
27 Correct 1326 ms 247656 KB Output is correct
28 Correct 1724 ms 247656 KB Output is correct
29 Correct 1702 ms 247656 KB Output is correct
30 Correct 878 ms 241776 KB Output is correct
31 Correct 451 ms 247532 KB Output is correct
32 Correct 950 ms 247660 KB Output is correct
33 Correct 607 ms 247656 KB Output is correct
34 Correct 904 ms 247656 KB Output is correct
35 Correct 585 ms 247660 KB Output is correct
36 Correct 739 ms 247660 KB Output is correct
37 Correct 538 ms 247660 KB Output is correct