Submission #729896

#	Time	Username	Problem	Language	Result	Execution time	Memory
729896		kthng	수족관 2 (KOI13_aqua2)	C++17	100 / 100	318 ms	32116 KiB

aqua2

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

static const int inf = 1e8;

int n, k;
pii a[300000];
int b[300000];
map<pii, int> mp;

pii tree[600004];

void update(int idx, int s, int e, int x, int val) {
	if (x < s || x > e) return;
	if (s == e) {
		tree[idx] = pii(val, x);
		return;
	}
	int m = s + e >> 1;
	update(idx << 1, s, m, x, val);
	update(idx << 1 | 1, m + 1, e, x, val);
	tree[idx] = min(tree[idx << 1], tree[idx << 1 | 1]);
}

pii get(int idx, int s, int e, int l, int r) {
	if (r < s || e < l) return pii(inf, -1);
	if (l <= s && e <= r) return tree[idx];
	int m = s + e >> 1;
	pii t0 = get(idx << 1, s, m, l, r);
	pii t1 = get(idx << 1 | 1, m + 1, e, l, r);
	return min(t0, t1);
}

long double f(int l, int r, int dep) {
	if (r < l) return 0;
	ll hole = b[r] - b[l - 1];
	if (hole == 0) return 0;
	ll width = a[r].first - a[l - 1].first;
	pii tmp = get(1, 1, n, l, r);
	ll height = tmp.first - dep;
	if (height < 0) height = 0;
	long double ret = width * (long double)height / (long double)hole;
	long double t0 = f(l, tmp.second - 1, tmp.first);
	long double t1 = f(tmp.second + 1, r, tmp.first);
	ret += max(t0, t1);
	return ret;
}

ll g(int l, int r, int dep) {
	if (r < l) return 0;
	ll hole = b[r] - b[l - 1];
	ll width = a[r].first - a[l - 1].first;
	pii tmp = get(1, 1, n, l, r);
	ll height = tmp.first - dep;
	if (height < 0) height = 0;
	ll ret = 0;
	if (hole == 0) ret = width * height;
	ll t0 = g(l, tmp.second - 1, tmp.first);
	ll t1 = g(tmp.second + 1, r, tmp.first);
	ret += t0;
	ret += t1;
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int t0, t1;
		scanf("%d%d", &t0, &t1);
		if (i & 1) continue;
		mp[pii(t0, t1)] = (i >> 1);
		a[(i >> 1)] = pii(t0, t1);
	}
	scanf("%d", &k);
	n >>= 1;
	n--;
	for (int i = 0; i <= 4 * n; i++) tree[i] = pii(inf, -1);
	for (int i = 0; i < k; i++) {
		int t0, t1, t2, t3;
		scanf("%d%d%d%d", &t0, &t1, &t2, &t3);
		b[mp[pii(t2, t3)]] = 1;
	}
	for (int i = 1; i <= n; i++) {
		b[i] = b[i - 1] + b[i];
		update(1, 1, n, i, a[i].second);
	}
	printf("%.2LF\n", f(1, n, 0));
	printf("%lld\n", g(1, n, 0));
	return 0;
}

Compilation message (stderr)

aqua2.cpp: In function 'void update(int, int, int, int, int)':
aqua2.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int m = s + e >> 1;
      |          ~~^~~
aqua2.cpp: In function 'pii get(int, int, int, int, int)':
aqua2.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int m = s + e >> 1;
      |          ~~^~~
aqua2.cpp: In function 'int main()':
aqua2.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
aqua2.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d", &t0, &t1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
aqua2.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
aqua2.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d%d", &t0, &t1, &t2, &t3);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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