oj.uz

Submission #479270

# Submission time Handle Problem Language Result Execution time Memory
479270 2021-10-11T05:07:41 Z 1bin 수족관 2 (KOI13_aqua2) C++14
100 / 100
 144 ms 24084 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6312 KB Output is correct
2 Correct 100 ms 6152 KB Output is correct
3 Correct 126 ms 11048 KB Output is correct
4 Correct 125 ms 16824 KB Output is correct
5 Correct 133 ms 18024 KB Output is correct
6 Correct 125 ms 24084 KB Output is correct
7 Correct 144 ms 21004 KB Output is correct
8 Correct 98 ms 18096 KB Output is correct
9 Correct 127 ms 15284 KB Output is correct
10 Correct 116 ms 14452 KB Output is correct