oj.uz

Submission #1013216

# Submission time Handle Problem Language Result Execution time Memory
1013216 2024-07-03T10:08:38 Z boris_mihov Comparing Plants (IOI20_plants) C++17
44 / 100
 1020 ms 116816 KB 
#include "plants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 18;
const int INF  = 2e9;

int n, k;
struct SegmentTree
{
    struct Node
    {
        int min;
        int idx;
        int lazy;

        Node()
        {
            min = INF;
            idx = -1;
            lazy = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            if (left.min < right.min)
            {
                return left;
            } else
            {
                return right;
            }
        }
    };

    Node tree[4*MAXN];
    void build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node].min = vals[l];
            tree[node].idx = l;
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node, vals);
        build(mid + 1, r, 2*node + 1, vals);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].min += tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void update(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = queryVal;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        update(l, mid, 2*node, queryL, queryR, queryVal);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }
    
    Node query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node result;
        int mid = l + r >> 1;
        if (queryL <= mid) result = result + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) result = result + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return result;
    }

    void build(int r[])
    {
        build(1, n, 1, r);
    }

    void update(int l, int r, int val)
    {
        update(1, n, 1, l, r, val);
    }

    Node query(int l, int r)
    {
        return query(1, n, 1, l, r);
    }
};

struct Fenwick
{
    int tree[MAXN];
    void reset()
    {
        std::fill(tree + 1, tree + 1 + n, 0);
    }

    void update(int idx, int val)
    {
        for (; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int idx)
    {
        int res = 0;
        for (; idx ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int kth(int k)
    {
        int idx = 0;
        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (idx + (1 << lg) <= n && tree[idx + (1 << lg)] < k)
            {
                idx += (1 << lg);
                k -= tree[idx];
            }
        }

        return idx + 1;
    }
};

int h[2 * MAXN];
struct Sparse
{
    int sparse[MAXLOG + 1][2 * MAXN];
    void build(int jump[])
    {
        for (int i = 1 ; i <= 2 * n ; ++i)
        {
            sparse[0][i] = jump[i];
        }

        for (int lg = 1 ; (1 << lg) <= 2 * n ; ++lg)
        {
            for (int u = 1 ; u <= 2 * n ; ++u)
            {
                sparse[lg][u] = sparse[lg - 1][sparse[lg - 1][u]];
            }
        }
    }

    bool jumpLeft(int from, int to)
    {
        for (int lg = MAXLOG ; lg >= 0 ; --lg)
        {
            if (sparse[lg][from] != 0 && sparse[lg][from] >= to)
            {
                from = sparse[lg][from];
            }
        }

        if (h[from] >= h[to]) return true;
        return false;
    }

    bool jumpRight(int from, int to)
    {
        for (int lg = MAXLOG ; lg >= 0 ; --lg)
        {
            if (sparse[lg][from] != 0 && sparse[lg][from] <= to)
            {
                from = sparse[lg][from];
            }
        }

        if (h[from] >= h[to]) return true;
        return false;
    }
};

Fenwick fenwick;
SegmentTree tree;
Sparse sparsePrev;
Sparse sparseNext;

int r[MAXN];
int prev[2 * MAXN];
int next[2 * MAXN];
int ptrH;

void rec(int idx)
{
    while (true)
    {
        SegmentTree::Node res;
        if (idx > 1) res = res + tree.query(std::max(1, idx - k + 1), idx - 1);
        if (idx < k) res = res + tree.query(n - (k - idx) + 1, n);
        if (res.min == 0)
        {
            rec(res.idx);
        } else
        {
            break;
        }
    }

    h[idx] = ptrH--;
    tree.update(idx, idx, 2 * n);
    if (idx > 1) tree.update(std::max(1, idx - k + 1), idx, -1);
    if (idx < k) tree.update(n - (k - idx) + 1, n, -1);
}

std::map <int,int> toIndex;
void init(int K, std::vector <int> R) 
{
    k = K;
    n = R.size();
    for (int i = 1 ; i <= n ; ++i)
    {
        r[i] = R[i - 1];
    }

    ptrH = n;
    tree.build(r);
    while (ptrH > 0)
    {
        SegmentTree::Node res = tree.query(1, n);
        assert(res.min == 0);
        rec(res.idx);
    }

    for (int i = n + 1 ; i <= 2 * n ; ++i)
    {
        h[i] = h[i - n];
    }

    for (int i = 1 ; i < k ; ++i)
    {
        fenwick.update(h[i], 1);
    }

    for (int i = k ; i <= 2 * n ; ++i)
    {
        if (fenwick.query(h[i]) == 0)
        {
            prev[i] = 0;
        } else
        {
            prev[i] = toIndex[fenwick.kth(fenwick.query(h[i]))];
        }

        toIndex[h[i - k + 1]] = 0;
        toIndex[h[i]] = i;

        fenwick.update(h[i - k + 1], -1);
        fenwick.update(h[i], 1);
    }

    fenwick.reset();
    for (int i = 2 * n ; i > 2 * n - k + 1 ; --i)
    {
        fenwick.update(h[i], 1);
    }

    toIndex.clear();
    for (int i = 2 * n - k + 1 ; i >= 1 ; --i)
    {
        if (fenwick.query(h[i]) == 0)
        {
            next[i] = 0;
        } else
        {
            next[i] = toIndex[fenwick.kth(fenwick.query(h[i]))];
        }

        toIndex[h[i + k - 1]] = 0;
        toIndex[h[i]] = i;

        fenwick.update(h[i + k - 1], -1);
        fenwick.update(h[i], 1);
    }

    sparsePrev.build(prev);
    sparseNext.build(next);
}

int compare_plants(int x, int y) 
{
	x++; y++;
    if (sparsePrev.jumpLeft(x + n, y) || sparseNext.jumpRight(x, y)) return 1;
    if (sparsePrev.jumpLeft(y, x) || sparseNext.jumpRight(y, n + x)) return -1;
    return 0;
}

Compilation message

plants.cpp: In member function 'void SegmentTree::build(int, int, int, int*)':
plants.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~
plants.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
plants.cpp:90:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int mid = l + r >> 1;
      |                   ~~^~~
plants.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, int, int)':
plants.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 3 ms 9844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 6 ms 10372 KB Output is correct
7 Correct 63 ms 15964 KB Output is correct
8 Correct 5 ms 10072 KB Output is correct
9 Correct 6 ms 10332 KB Output is correct
10 Correct 56 ms 16208 KB Output is correct
11 Correct 59 ms 16212 KB Output is correct
12 Correct 79 ms 16212 KB Output is correct
13 Correct 55 ms 15956 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 6 ms 10372 KB Output is correct
7 Correct 63 ms 15964 KB Output is correct
8 Correct 5 ms 10072 KB Output is correct
9 Correct 6 ms 10332 KB Output is correct
10 Correct 56 ms 16208 KB Output is correct
11 Correct 59 ms 16212 KB Output is correct
12 Correct 79 ms 16212 KB Output is correct
13 Correct 55 ms 15956 KB Output is correct
14 Correct 121 ms 21588 KB Output is correct
15 Correct 888 ms 90852 KB Output is correct
16 Correct 110 ms 21464 KB Output is correct
17 Correct 865 ms 90964 KB Output is correct
18 Correct 553 ms 102600 KB Output is correct
19 Correct 505 ms 90448 KB Output is correct
20 Correct 613 ms 89684 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 66 ms 14564 KB Output is correct
4 Correct 563 ms 97632 KB Output is correct
5 Correct 670 ms 93268 KB Output is correct
6 Correct 867 ms 92312 KB Output is correct
7 Correct 999 ms 92496 KB Output is correct
8 Correct 1020 ms 91744 KB Output is correct
9 Correct 612 ms 95208 KB Output is correct
10 Correct 637 ms 94440 KB Output is correct
11 Correct 419 ms 116816 KB Output is correct
12 Correct 584 ms 91940 KB Output is correct
13 Correct 552 ms 109008 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Incorrect 4 ms 9884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Incorrect 3 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Incorrect 3 ms 9844 KB Output isn't correct
5 Halted 0 ms 0 KB -