oj.uz

답안 #705952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705952 2023-03-05T17:03:31 Z finn__ 식물 비교 (IOI20_plants) C++17
0 / 100
 57 ms 3548 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct SegmentTreeMin
{
    vector<pair<int64_t, int64_t>> t;
    vector<int64_t> z;
    int64_t l, n;

    SegmentTreeMin(vector<int> v)
    {
        n = v.size();
        l = 1 << (32 - __builtin_clz(v.size()));
        t = vector<pair<int64_t, int64_t>>(2 * l, make_pair(INT64_MAX, INT64_MAX));
        z = vector<int64_t>(2 * l, 0);

        for (int64_t i = l; i < l + n; i++)
            t[i] = {v[i - l], i - l};
        for (int64_t i = l - 1; i; i--)
        {
            t[i] = min(t[2 * i], t[2 * i + 1]);
            if (t[2 * i].first == t[2 * i + 1].first)
                t[i] = t[2 * i + 1];
        }
    }

    void propagate(int64_t k)
    {
        t[2 * k].first -= z[k], t[2 * k + 1].first -= z[k];
        z[2 * k] += z[k], z[2 * k + 1] += z[k];
        z[k] = 0;
    }

private:
    void decrement(int64_t i, int64_t j, int64_t k, int64_t x, int64_t y)
    {
        if (y <= i || x >= j)
            return;
        if (i <= x && y <= j)
        {
            t[k].first--;
            z[k]++;
        }
        else
        {
            propagate(k);
            decrement(i, j, 2 * k, x, (x + y) / 2);
            decrement(i, j, 2 * k + 1, (x + y) / 2, y);
            t[k] = min(t[2 * k], t[2 * k + 1]);
            if (t[2 * k].first == t[2 * k + 1].first)
                t[k] = t[2 * k + 1];
        }
    }

    pair<int64_t, int64_t> range_min(int64_t i, int64_t j, int64_t k, int64_t x, int64_t y)
    {
        if (y <= i || x >= j)
            return make_pair(INT64_MAX, INT64_MAX);
        if (i <= x && y <= j)
            return t[k];

        propagate(k);
        return min(range_min(i, j, 2 * k, x, (x + y) / 2),
                   range_min(i, j, 2 * k + 1, (x + y) / 2, y));
    }

public:
    void decrement(int64_t i, int64_t j)
    {
        if (i < 0)
            i += n;
        if (j < 0)
            j += n;
        if (i >= j)
        {
            decrement(0, j, 1, 0, l);
            decrement(i, n, 1, 0, l);
        }
        else
            decrement(i, j, 1, 0, l);
    }

    pair<int64_t, int64_t> range_min(int64_t i, int64_t j)
    {
        if (i < 0)
            i += n;
        if (j < 0)
            j += n;
        if (i >= j)
        {
            return min(range_min(0, j, 1, 0, l),
                       range_min(i, n, 1, 0, l));
        }
        else
            return range_min(i, j, 1, 0, l);
    }

    void set_inf(int64_t i, int64_t k, int64_t x, int64_t y)
    {
        if (y - x == 1)
        {
            t[k] = {INT64_MAX, INT64_MAX};
            return;
        }
        if (i < (x + y) / 2)
            set_inf(i, 2 * k, x, (x + y) / 2);
        else
            set_inf(i, 2 * k + 1, (x + y) / 2, y);
        t[k] = min(t[2 * k], t[2 * k + 1]);
    }
};

vector<int64_t> h;
vector<vector<int64_t>> left_anc, right_anc, left_d, right_d;
int64_t k_;

int64_t find_height(int64_t i, int64_t k, SegmentTreeMin &tree, int64_t p)
{
    auto [pre, j] = tree.range_min(i - k + 1, i);
    while (!pre)
    {
        p = find_height(j, k, tree, p);
        tie(pre, j) = tree.range_min(i - k + 1, i);
    }
    h[i] = p++;
    tree.decrement(i - k + 1, i);
    tree.set_inf(i, 1, 0, tree.l);
    return p;
}

void init(int k, std::vector<int> r)
{
    k_ = k;
    h = vector<int64_t>(r.size());
    SegmentTreeMin tree(r);

    int64_t p = 0;
    while (p < r.size())
        p = find_height(tree.range_min(0, r.size()).second, k, tree, p);

    set<pair<int64_t, int64_t>> s;
    left_anc = vector<vector<int64_t>>(r.size());
    right_anc = vector<vector<int64_t>>(r.size());
    left_d = vector<vector<int64_t>>(r.size());
    right_d = vector<vector<int64_t>>(r.size());
    for (size_t i = 0; i + 1 < k; i++)
        s.emplace(h[i], i);

    for (int64_t i = 0; i < r.size(); i++)
    {
        int64_t const j = (i + k - 1) % r.size();
        auto it = s.upper_bound(make_pair(h[j], j));
        if (it != s.end())
            left_anc[j].push_back(it->second), left_d[j].push_back(abs(j - it->second));
        s.emplace(h[j], j);
        s.erase(make_pair(h[i], i));
        it = s.upper_bound(make_pair(h[i], i));
        if (it != s.end())
            right_anc[i].push_back(it->second), right_d[i].push_back(abs(it->second - i));
    }

    for (int64_t j = 1; j <= 32 - __builtin_clz(r.size()); j++)
        for (size_t i = 0; i < r.size(); i++)
        {
            if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
            {
                left_anc[i][j] = left_anc[left_anc[i][j - 1]][j - 1];
                left_d[i][j] = left_d[i][j - 1] + left_d[left_anc[i][j - 1]][j - 1];
            }
            if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
            {
                right_anc[i][j] = right_anc[right_anc[i][j - 1]][j - 1];
                right_d[i][j] = right_d[i][j - 1] + right_d[right_anc[i][j - 1]][j - 1];
            }
        }
}

bool plant_is_greater(
    int64_t x, int64_t y, vector<vector<int64_t>> const &anc,
    vector<vector<int64_t>> const &dis, bool dir)
{
    int64_t d = (y - x) * (dir ? -1 : 1);
    if (d < 0)
        d += anc.size();
    for (int64_t i = (int64_t)anc[x].size() - 1; i >= 0; i--)
        if (dis[x][i] <= d)
        {
            d -= dis[x][i];
            x = anc[x][i];
        }

    return d < k_ && h[x] <= h[y];
}

int compare_plants(int x, int y)
{
    if (x == y)
        return 0;
    if (plant_is_greater(x, y, left_anc, left_d, 1))
        return 1;
    if (plant_is_greater(x, y, right_anc, right_d, 0))
        return 1;
    if (plant_is_greater(y, x, left_anc, left_d, 1))
        return -1;
    if (plant_is_greater(y, x, right_anc, right_d, 0))
        return -1;
    return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:139:14: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     while (p < r.size())
      |            ~~^~~~~~~~~~
plants.cpp:147:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  147 |     for (size_t i = 0; i + 1 < k; i++)
      |                        ~~~~~~^~~
plants.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int64_t i = 0; i < r.size(); i++)
      |                         ~~^~~~~~~~~~
plants.cpp:166:36: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  166 |             if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
      |                 ~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:166:80: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  166 |             if (left_anc[i].size() == j && left_anc[left_anc[i][j - 1]].size() == j)
      |                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:171:37: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  171 |             if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
      |                 ~~~~~~~~~~~~~~~~~~~~^~~~
plants.cpp:171:83: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  171 |             if (right_anc[i].size() == j && right_anc[right_anc[i][j - 1]].size() == j)
      |                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 57 ms 2984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 55 ms 3548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 57 ms 2984 KB Output isn't correct
7 Halted 0 ms 0 KB -