Submission #251984

#	Time	Username	Problem	Language	Result	Execution time	Memory
251984		iriszero	수족관 2 (KOI13_aqua2)	C++17	0 / 100	217 ms	18512 KiB

aqua2

#include <stdio.h>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>

#define MX 300005

using namespace std;
typedef long long ll;
double max(double a, double b) { return a>b? a: b; }
int min(int a, int b) { return a<b? a: b;}

int N, M;
int x[MX], y[MX];

const int ORDER_INF = MX * 55;
vector<int> order(MX, ORDER_INF);
vector<int> inv_order(MX, -1);

int min_order_tree[MX * 4];
int tree_len, tree_r, tree_n;

int accum_hole[MX];

// order[] should have been filled
void build_order_tree(int sz) {
    tree_len = 1; tree_r = 1; tree_n = sz;
    while ( tree_r < tree_n) {
        tree_r *= 2;
        tree_len += tree_r;
    }
    for (int i=1; i<=tree_n; i++) {
        min_order_tree[tree_len - tree_r + i] = order[i];
    }
    for (int i=tree_n+1; i<=tree_r; i++) {
        min_order_tree[tree_len - tree_r + i] = ORDER_INF;
    }
    for (int i=tree_len - tree_r; i>=1; i--) {
        min_order_tree[i] = min(min_order_tree[i*2], min_order_tree[i*2+1]);
    }
}

int get_lowest_order(int start, int end) {
    start += tree_len - tree_r;
    end += tree_len - tree_r;

    int ans = ORDER_INF;
    while (start <= end) {
        if (start % 2 == 1) {
            ans = min(ans, min_order_tree[start]);
            start++;
        }
        if (end % 2 == 0) {
            ans = min(ans, min_order_tree[end]);
            end--;
        }
        start /= 2;
        end /= 2;
    }
    return ans;
}

int get_hole_count(int start, int end) {
    return accum_hole[end] - accum_hole[start-1];
}

double solve(const int start, const int end, const ll height, ll &residue) {
    if (start > end) return 0;
    const int lowest_order = get_lowest_order(start, end);
    if (lowest_order == ORDER_INF) {
        for (int i = start; i<=end; i++) {
            residue += ll(y[i] - height) * ll(x[i+1] - x[i]);
        }
        return 0;
    }
    const int mid = inv_order[lowest_order];
    double elapsed_time = double(x[end+1] - x[start]) * double(y[mid] - height) / double(get_hole_count(start, end));
    return elapsed_time + max(solve(start, mid-1, y[mid], residue), solve(mid+1, end, y[mid], residue));
}

int main(void) {
    scanf("%d", &N);

    //trash
    {
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        assert(t1 == 0  && t2 == 0);
    }

    map<int, int> x_inv;
    for (int i=1; i<=N/2-1; i++) {
        int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        x[i] = x1;
        x_inv[x1] = i;
        y[i] = y1;
    }

    //trash
    {
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        x[N/2] = t1;
        x_inv[t1] = N/2;
        assert(t2 == 0);
    }

    scanf("%d", &M);
    vector<pair<int, int>> vec_p_y_idx;

    for (int i=0; i<M; i++) {
        int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        assert(y1 == y2);

        vec_p_y_idx.push_back({y1, x_inv[x1]});
    };
    sort(vec_p_y_idx.begin(), vec_p_y_idx.end());

    int cnt = 1;
    for (const auto &p_y_idx : vec_p_y_idx) {
        order[p_y_idx.second] = cnt;
        inv_order[cnt] = p_y_idx.second;
        cnt += 1;
    }

    for (int i=1; i<=N/2-1; i++) {
        accum_hole[i] = accum_hole[i-1] + (order[i] < ORDER_INF);
    }
    build_order_tree(N/2-1);

    ll residue = 0;
    double time = solve(1, N/2-1, 0, residue);
    printf("%.2lf\n%lld", time, residue);
}

Compilation message (stderr)

aqua2.cpp: In function 'int main()':
aqua2.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
aqua2.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
aqua2.cpp:95:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
aqua2.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &M);
     ~~~~~^~~~~~~~~~
aqua2.cpp:114:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 35
• Subtask 4: 0 / 31