Submission #836207

#	Time	Username	Problem	Language	Result	Execution time	Memory
836207		finn__	Quality Of Living (IOI10_quality)	C++17	80 / 100	5047 ms	262144 KiB

quality

#include <bits/stdc++.h>

#include "quality.h"

using namespace std;

template <typename T, int64_t N>
struct FenwickTree
{
    T t[N][N];

    void update(int64_t i, int64_t j, T x)
    {
        ++i;
        while (i <= N)
        {
            int64_t k = j + 1;
            while (k <= N)
            {
                t[i - 1][k - 1] += x;
                k += k & -k;
            }
            i += i & -i;
        }
    }

    T prefix_sum(int64_t i, int64_t j)
    {
        T x = 0;
        ++i;
        while (i)
        {
            int64_t k = j + 1;
            while (k)
            {
                x += t[i - 1][k - 1];
                k -= k & -k;
            }
            i -= i & -i;
        }
        return x;
    }

    T range_sum(int64_t i1, int64_t i2, int64_t j1, int64_t j2)
    {
        return prefix_sum(i2, j2) - (i1 ? prefix_sum(i1 - 1, j2) : 0) - (j1 ? prefix_sum(i2, j1 - 1) : 0) +
               (i1 && j1 ? prefix_sum(i1 - 1, j1 - 1) : 0);
    }
};

constexpr size_t R = 3000;

FenwickTree<int, R> tree;
int median[R][R], k;
vector<pair<int, int>> order;

void parallel_bsearch(vector<pair<int, int>> const &q, int H, int W, int a, int b)
{
    if (a == b)
    {
        for (auto const &[i, j] : q)
            median[i][j] = a;
        return;
    }

    int const mid = (a + b) / 2;
    while (k < mid)
        ++k, tree.update(order[k].first, order[k].second, 1);
    while (k > mid)
        tree.update(order[k].first, order[k].second, -1), --k;

    vector<pair<int, int>> left_q, right_q;
    for (auto const &[i, j] : q)
    {
        int num_leq = tree.range_sum(i, i + H - 1, j, j + W - 1);
        if (num_leq < (H * W) / 2 + 1)
            right_q.emplace_back(i, j);
        else
            left_q.emplace_back(i, j);
    }

    if (!left_q.empty())
        parallel_bsearch(left_q, H, W, a, (a + b) / 2);
    if (!right_q.empty())
        parallel_bsearch(right_q, H, W, (a + b) / 2 + 1, b);
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    order.resize(R * C + 1);
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            order[Q[i][j]] = {i, j};
    vector<pair<int, int>> queries;
    for (int i = 0; i < R - H + 1; ++i)
        for (int j = 0; j < C - W + 1; ++j)
            queries.emplace_back(i, j);

    parallel_bsearch(queries, H, W, 1, R * C);

    int ans = INT_MAX;
    for (int i = 0; i < R - H + 1; ++i)
        for (int j = 0; j < C - W + 1; ++j)
            ans = min(ans, median[i][j]);
    return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20