oj.uz

답안 #320637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320637 2020-11-09T11:17:34 Z tjdgus4384 수족관 2 (KOI13_aqua2) C++14
69 / 100
 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 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

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 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

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 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 -