Submission #320641

#	Time	Username	Problem	Language	Result	Execution time	Memory
320641		tjdgus4384	수족관 2 (KOI13_aqua2)	C++14	100 / 100	334 ms	46272 KiB

aqua2

#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 (stderr)

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 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31