Submission #479270

#	Time	Username	Problem	Language	Result	Execution time	Memory
479270		1bin	수족관 2 (KOI13_aqua2)	C++14	100 / 100	144 ms	24084 KiB

aqua2

#include <bits/stdc++.h>
#include <cassert>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, x[NMAX], xx[NMAX], y[NMAX], chk[NMAX], b, base = 1, k, a, c;
ll ps[NMAX], ans;
vector<pair<int, int>> seg;
vector<pair<int, int>> v;

void update(int idx, int val) {
	idx += base;
	seg[idx] = { val, idx - base }; idx /= 2;
	while (idx) {
		seg[idx] = seg[idx * 2];
		if (seg[idx * 2 + 1].first < seg[idx].first) seg[idx] = seg[idx * 2 + 1];
		idx /= 2;
	}
	return;
}

int find(int l, int r) {
	l += base; r += base;
	int h = 2e9, ret;
	while (l <= r) {
		if (l & 1) {
			if (seg[l].first < h) h = seg[l].first, ret = seg[l].second;
			l++;
		}
		if (!(r & 1)) {
			if (seg[r].first < h) h = seg[r].first, ret = seg[r].second;
			r--;
		}
		l /= 2; r /= 2;
	}
	return ret;
}

double go(int l, int r, int h) {
	if (l > r) return 0;
	double t = 0;
	int lx = x[l], rx = xx[r], ix;
	int p = chk[r] - ((l) ? chk[l - 1] : 0); 
	if (!p) {
		ans += ps[r] - ((l) ? ps[l - 1] : 0) - 1LL * h * (rx - lx);
		return 0;
	}
	ix = find(l, r);
	assert(ix >= l && ix <= r);
	double ret = 1.0 * (y[ix] - h) * (rx - lx) / p;
	t = max(go(l, ix - 1, y[ix]), go(ix + 1, r, y[ix]));
	return ret + t;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout << fixed; cout.precision(2);

	cin >> n >> b >> b; n = (n - 2) / 2;
	while (base < n) base *= 2;
	seg.resize(base * 2);

	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> xx[i] >> y[i];
		update(i, y[i]);
		ps[i] = (xx[i] - x[i]) * y[i];
		if (i) ps[i] += ps[i - 1];
	}
	cin >> b >> b;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> a >> c >> b >> c;
		v.emplace_back(a, b);
	}
	sort(all(v));
	int ix = 0;
	for (int i = 0; i < n; i++) {
		if (ix < k && v[ix] == make_pair(x[i], xx[i])) {
			chk[i] = 1; ix++;
		}
		if (i) chk[i] += chk[i - 1];
	}
	cout << go(0, n - 1, 0) << '\n';
	cout << ans;
	return 0;
}

Compilation message (stderr)

aqua2.cpp: In function 'int find(int, int)':
aqua2.cpp:39:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |  return ret;
      |         ^~~

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31