oj.uz

Submission #836227

# Submission time Handle Problem Language Result Execution time Memory
836227 2023-08-24T08:58:41 Z finn__ Quality Of Living (IOI10_quality) C++17
100 / 100
 3873 ms 224428 KB 
#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 k;
uint16_t order[R * R + 1][2];

int parallel_bsearch(vector<pair<int, int>> &&q, int H, int W, int a, int b)
{
    if (a == b)
        return a;

    int const mid = (a + b) / 2;
    while (k < mid)
        ++k, tree.update(order[k][0], order[k][1], 1);
    while (k > mid)
        tree.update(order[k][0], order[k][1], -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);
    }

    vector<pair<int, int>>().swap(q);
    if (!left_q.empty())
        return parallel_bsearch(move(left_q), H, W, a, (a + b) / 2);
    return parallel_bsearch(move(right_q), H, W, (a + b) / 2 + 1, b);
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            order[Q[i][j]][0] = i, order[Q[i][j]][1] = 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);

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2232 KB Output is correct
6 Correct 2 ms 2012 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2232 KB Output is correct
6 Correct 2 ms 2012 KB Output is correct
7 Correct 21 ms 6796 KB Output is correct
8 Correct 15 ms 6340 KB Output is correct
9 Correct 23 ms 6848 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2232 KB Output is correct
6 Correct 2 ms 2012 KB Output is correct
7 Correct 21 ms 6796 KB Output is correct
8 Correct 15 ms 6340 KB Output is correct
9 Correct 23 ms 6848 KB Output is correct
10 Correct 355 ms 31580 KB Output is correct
11 Correct 196 ms 24860 KB Output is correct
12 Correct 163 ms 24568 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 820 KB Output is correct
2 Correct 1 ms 816 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 3 ms 2112 KB Output is correct
5 Correct 3 ms 2232 KB Output is correct
6 Correct 2 ms 2012 KB Output is correct
7 Correct 21 ms 6796 KB Output is correct
8 Correct 15 ms 6340 KB Output is correct
9 Correct 23 ms 6848 KB Output is correct
10 Correct 355 ms 31580 KB Output is correct
11 Correct 196 ms 24860 KB Output is correct
12 Correct 163 ms 24568 KB Output is correct
13 Correct 3245 ms 145376 KB Output is correct
14 Correct 2832 ms 109712 KB Output is correct
15 Correct 3873 ms 224428 KB Output is correct