| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131119 |
2019-07-16T14:37:16 Z |
tjdgus4384 |
수족관 2 (KOI13_aqua2) |
C++14 |
|
943 ms |
68000 KB |
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[500001];
int seg[2000001], seg1, lefted;
int h1[500001];
int n, x1[300001], y2[300001], k, a, b, c, d;
void update(int left, int right, int node, int start, int end){
if(left >= end || right <= start) return;
seg[node]++;
int mid = (left+right)/2;
if(mid == left || mid == right) return;
update(left, mid, node*2, start, end);
update(mid, right, node*2+1, start, end);
}
int get(int left, int right, int node, int start, int end){
if(left >= end || right <= start) return 0;
if(right <= end && left >= start) return seg[node];
if(left < start || right > end){
int mid = (left+right)/2;
int ans = max(get(left, mid, node*2, start, end) , get(mid, right, node*2+1, start, end));
}
}
double solve(int x, int y, int h){
if(x >= y) return 0;
double ans = 0;
int k = get(0, seg1, 1, x, y);
if(k == 0){
for(int i = x;i < y;i++){
lefted += h1[i] - h;
}
return 0;
}
bool chk = false;
for(int i = 0;i < v[h].size();i++){
if(v[h][i].first >= x && v[h][i].second <= y){
ans += solve(x, v[h][i].first, h);
x = v[h][i].second;
chk = true;
}
}
if(chk) ans += solve(x, y, h);
else ans = solve(x, y, h + 1) + (y - x) / k;
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 0;i < n;i++){
scanf("%d %d", &x1[i], &y2[i]);
if(i == 0) continue;
if(y2[i] == y2[i - 1]){
bool chk = false;
if(x1[i - 1] > x1[i]) {swap(x1[i - 1], x1[i]);chk = true;}
v[y2[i]].push_back({x1[i - 1], x1[i]});
for(int j = x1[i - 1];j < x1[i];j++) h1[j] = y2[i];
if(chk) swap(x1[i - 1], x1[i]);
}
}
seg1 = x1[n - 1];
scanf("%d", &k);
for(int i = 0;i < k;i++){
scanf("%d %d %d %d", &a, &b, &c, &d);
update(0, x1[n - 1], 1, a, c);
}
printf("%.2lf\n", solve(0, x1[n - 1], 0));
printf("%d", lefted);
return 0;
}
Compilation message
aqua2.cpp: In function 'int get(int, int, int, int, int)':
aqua2.cpp:21:13: warning: unused variable 'ans' [-Wunused-variable]
int ans = max(get(left, mid, node*2, start, end) , get(mid, right, node*2+1, start, end));
^~~
aqua2.cpp: In function 'double solve(int, int, int)':
aqua2.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < v[h].size();i++){
~~^~~~~~~~~~~~~
aqua2.cpp: In function 'int get(int, int, int, int, int)':
aqua2.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
aqua2.cpp: In function 'int main()':
aqua2.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
aqua2.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x1[i], &y2[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
aqua2.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &a, &b, &c, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12280 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
12152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
44304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
943 ms |
68000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
