oj.uz

Submission #729896

# Submission time Handle Problem Language Result Execution time Memory
729896 2023-04-24T19:00:54 Z kthng 수족관 2 (KOI13_aqua2) C++17
100 / 100
 318 ms 32116 KB 
#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

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

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

Subtask #2
21.0 / 21.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 4 ms 592 KB Output is correct
5 Correct 4 ms 676 KB Output is correct
6 Correct 5 ms 844 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 796 KB Output is correct
9 Correct 3 ms 572 KB Output is correct
10 Correct 3 ms 596 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 14144 KB Output is correct
2 Correct 257 ms 19808 KB Output is correct
3 Correct 318 ms 25408 KB Output is correct
4 Correct 267 ms 24648 KB Output is correct
5 Correct 304 ms 25480 KB Output is correct
6 Correct 227 ms 32116 KB Output is correct
7 Correct 270 ms 28932 KB Output is correct
8 Correct 217 ms 26592 KB Output is correct
9 Correct 278 ms 22568 KB Output is correct
10 Correct 277 ms 21964 KB Output is correct