| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 320637 |
2020-11-09T11:17:34 Z |
tjdgus4384 |
수족관 2 (KOI13_aqua2) |
C++14 |
|
1000 ms |
37564 KB |
#include<bits/stdc++.h>
using namespace std;
long long N, M, K, x3, y3, x2, y2, sum, line[1000001], tree[1000001], num[500001];
vector<pair<long long, long long> > w;
vector<long long> g[500001];
void lineUpd(long long start, long long end, long long node, long long index, long long x){
if(start > index || index > end) return;
if(start == end) {line[node] = x; return;}
long long mid = (start+end)/2;
lineUpd(start, mid, node*2, index, x);
lineUpd(mid+1, end, node*2+1, index, x);
line[node] = min(line[node*2], line[node*2+1]);
}
long long lineQuery(long long start, long long end, long long node, long long left, long long right){
if(start > right || end < left) return 1000000000;
if(left <= start && end <= right) return line[node];
long long mid = (start+end)/2;
return min(lineQuery(start, mid, node*2, left, right), lineQuery(mid+1, end, node*2+1, left, right));
}
void treeUpd(long long start, long long end, long long node, long long index, long long x){
if(start > index || index > end) return;
if(start == end) {tree[node] += x; return;}
long long mid = (start+end)/2;
treeUpd(start, mid, node*2, index, x);
treeUpd(mid+1, end, node*2+1, index, x);
tree[node] = tree[node*2] + tree[node*2+1];
}
long long treeQuery(long long start, long long end, long long node, long long left, long long right){
if(start > right || end < left) return 0;
if(left <= start && end <= right) return tree[node];
long long mid = (start+end)/2;
return treeQuery(start, mid, node*2, left, right) + treeQuery(mid+1, end, node*2+1, left, right);
}
double solve(long long s, long long e, long long h){
long long cnt = treeQuery(0, M-1, 1, s, e-1);
if(cnt == 0) return 0;
long long h2 = lineQuery(0, M-1, 1, s, e-1);
double ret = (double)(h2-h)*(w[e*2+1].first-w[s*2+1].first)/cnt;
sum -= (h2-h)*(w[e*2+1].first-w[s*2+1].first);
double retnext = 0;
long long s1 = s;
for(long long i = 0;i < g[h2].size();i++){
if(s <= g[h2][i] && g[h2][i] < e){
retnext = max(retnext, solve(s1, g[h2][i], h2));
s1 = g[h2][i]+1;
}
}
retnext = max(retnext, solve(s1, e, h2));
return ret + retnext;
}
int main(){
scanf("%lld", &N);
for(long long i = 0;i < N;i++){
scanf("%lld %lld", &x3, &y3);
w.push_back({x3, y3});
if(i > 0 && i%2 == 0){
g[w.back().second].push_back(M);
num[w[w.size()-2].first] = M++;
sum += w.back().second*(w.back().first - w[w.size()-2].first);
}
}
for(long long i = 0;i < M;i++){
lineUpd(0, M-1, 1, i, w[i*2+1].second);
}
scanf("%lld", &K);
for(long long i = 0;i < K;i++){
scanf("%lld %lld %lld %lld", &x3, &y3, &x2, &y2);
treeUpd(0, M-1, 1, num[x3], 1);
}
double ans = solve(0, M, 0);
printf("%.2lf\n%lld", ans, sum);
}
Compilation message
aqua2.cpp: In function 'double solve(long long int, long long int, long long int)':
aqua2.cpp:49:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(long long i = 0;i < g[h2].size();i++){
| ~~^~~~~~~~~~~~~~
aqua2.cpp: In function 'int main()':
aqua2.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%lld", &N);
| ~~~~~^~~~~~~~~~~~
aqua2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
62 | scanf("%lld %lld", &x3, &y3);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%lld", &K);
| ~~~~~^~~~~~~~~~~~
aqua2.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%lld %lld %lld %lld", &x3, &y3, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12140 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12136 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 7 |
Correct |
10 ms |
12140 KB |
Output is correct |
| 8 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12140 KB |
Output is correct |
| 10 |
Correct |
8 ms |
12140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12268 KB |
Output is correct |
| 4 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 5 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 6 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 7 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 8 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 9 |
Correct |
10 ms |
12140 KB |
Output is correct |
| 10 |
Correct |
9 ms |
12140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
15852 KB |
Output is correct |
| 2 |
Correct |
14 ms |
15852 KB |
Output is correct |
| 3 |
Correct |
17 ms |
16108 KB |
Output is correct |
| 4 |
Correct |
13 ms |
16108 KB |
Output is correct |
| 5 |
Correct |
14 ms |
16108 KB |
Output is correct |
| 6 |
Correct |
16 ms |
16364 KB |
Output is correct |
| 7 |
Correct |
16 ms |
16236 KB |
Output is correct |
| 8 |
Correct |
15 ms |
16108 KB |
Output is correct |
| 9 |
Correct |
14 ms |
16108 KB |
Output is correct |
| 10 |
Correct |
13 ms |
16108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
33992 KB |
Output is correct |
| 2 |
Correct |
289 ms |
33644 KB |
Output is correct |
| 3 |
Execution timed out |
1056 ms |
37564 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
