| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 729861 |
2023-04-24T18:20:55 Z |
kthng |
수족관 1 (KOI13_aqua1) |
C++17 |
|
2 ms |
544 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);
}
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;
double ret = width * height / (double)hole;
double t0 = f(l, tmp.second - 1, tmp.first);
double t1 = f(tmp.second + 1, r, tmp.first);
ret += t0;
ret += 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
aqua1.cpp: In function 'void update(int, int, int, int, int)':
aqua1.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int m = s + e >> 1;
| ~~^~~
aqua1.cpp: In function 'pii get(int, int, int, int, int)':
aqua1.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int m = s + e >> 1;
| ~~^~~
aqua1.cpp: In function 'int main()':
aqua1.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
aqua1.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d%d", &t0, &t1);
| ~~~~~^~~~~~~~~~~~~~~~~~
aqua1.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
aqua1.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d%d%d", &t0, &t1, &t2, &t3);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
