oj.uz

Submission #320641

# Submission time Handle Problem Language Result Execution time Memory
320641 2020-11-09T11:24:21 Z tjdgus4384 수족관 2 (KOI13_aqua2) C++14
100 / 100
 334 ms 46272 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;
    long long j = lower_bound(g[h2].begin(), g[h2].end(), s) - g[h2].begin();

    for(long long i = j;i < g[h2].size();i++){
        if(g[h2][i] >= e) break;
        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:51: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]
   51 |     for(long long i = j;i < g[h2].size();i++){
      |                         ~~^~~~~~~~~~~~~~
aqua2.cpp: In function 'int main()':
aqua2.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
aqua2.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%lld %lld", &x3, &y3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%lld", &K);
      |     ~~~~~^~~~~~~~~~~~
aqua2.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%lld %lld %lld %lld", &x3, &y3, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 8 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 8 ms 12140 KB Output is correct
7 Correct 8 ms 12140 KB Output is correct
8 Correct 8 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

# 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 12160 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 10 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 9 ms 12268 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15724 KB Output is correct
2 Correct 13 ms 15724 KB Output is correct
3 Correct 14 ms 15980 KB Output is correct
4 Correct 13 ms 16108 KB Output is correct
5 Correct 13 ms 16108 KB Output is correct
6 Correct 16 ms 16384 KB Output is correct
7 Correct 14 ms 15980 KB Output is correct
8 Correct 14 ms 15980 KB Output is correct
9 Correct 14 ms 15980 KB Output is correct
10 Correct 13 ms 16108 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 27976 KB Output is correct
2 Correct 275 ms 27888 KB Output is correct
3 Correct 288 ms 30780 KB Output is correct
4 Correct 248 ms 36796 KB Output is correct
5 Correct 281 ms 37436 KB Output is correct
6 Correct 263 ms 46272 KB Output is correct
7 Correct 261 ms 38460 KB Output is correct
8 Correct 172 ms 36156 KB Output is correct
9 Correct 334 ms 39484 KB Output is correct
10 Correct 305 ms 39104 KB Output is correct