Submission #213534

#	Time	Username	Problem	Language	Result	Execution time	Memory
213534		spdskatr	Palembang Bridges (APIO15_bridge)	C++14	9 / 100	108 ms	188408 KiB

bridge

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <utility>
#include <cstring>
#include <vector>
#include <cassert>
#define MAX ((1<<30)-1)
#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[8000005], lazy[8000005];
	int lc[8000005], rc[8000005], 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) {
		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) {
			//printf("seg_sum(%d, %d, %d, %d): %lld\n", lo, hi, x, ind, st[ind]);
			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]);
		//printf("seg_sum(%d, %d, %d, %d): %lld\n", lo, hi, x, ind, res);
		return res;
	}
	void seg_inc(int lo, int hi, int l, int r, long long val, int ind) {
		lu(lo, hi, ind);
		assert(lo < r && hi > l);
		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]);
		}
		assert(lazy[ind] == 0);
		lu(lo, mid, lc[ind]);
		lu(mid, hi, rc[ind]);
		st[ind] = st[lc[ind]] + st[rc[ind]];
	}
	void dump_state() {
		printf("State:");
		for (int i = 0; i < 10; i++) printf(" %d", seg_sum(0, MAX, i, 1));
		printf("\n");
		printf("Grand total: %lld\n", seg_sum(0, MAX, MAX-1, 1));
	}
	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, i });
		ins({ r, i });
		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();
		//printf("pref[%d]: %d\n", i+1, pref[i+1]);
	}
	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();
		//printf("suff[%d]: %d\n", i+1, suff[i+1]);
	}
	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 (stderr)

bridge.cpp: In member function 'void DS::dump_state()':
bridge.cpp:82:67: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   for (int i = 0; i < 10; i++) printf(" %d", seg_sum(0, MAX, i, 1));
                                              ~~~~~~~~~~~~~~~~~~~~~^
bridge.cpp: In function 'int main()':
bridge.cpp:120: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:124: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: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 9 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37