oj.uz

Submission #1013220

# Submission time Handle Problem Language Result Execution time Memory
1013220 2024-07-03T10:09:46 Z boris_mihov Comparing Plants (IOI20_plants) C++17
100 / 100
 1112 ms 116400 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 (from - k + 1 <= to && 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 (from + k - 1 >= to && 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);
        rec(res.idx);
    }

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

    for (int i = 1 ; i < k ; ++i)
    {
        toIndex[h[i]] = 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);
    }

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

    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
5.0 / 5.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 3 ms 9832 KB Output is correct
4 Correct 5 ms 9952 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 48 ms 13600 KB Output is correct
7 Correct 98 ms 21428 KB Output is correct
8 Correct 453 ms 91476 KB Output is correct
9 Correct 436 ms 91444 KB Output is correct
10 Correct 467 ms 91988 KB Output is correct
11 Correct 487 ms 95824 KB Output is correct
12 Correct 503 ms 104528 KB Output is correct
13 Correct 533 ms 116400 KB Output is correct
14 Correct 539 ms 90628 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 4 ms 9784 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9816 KB Output is correct
5 Correct 4 ms 10072 KB Output is correct
6 Correct 7 ms 10296 KB Output is correct
7 Correct 66 ms 15700 KB Output is correct
8 Correct 5 ms 10072 KB Output is correct
9 Correct 6 ms 10188 KB Output is correct
10 Correct 70 ms 15544 KB Output is correct
11 Correct 63 ms 15700 KB Output is correct
12 Correct 103 ms 15800 KB Output is correct
13 Correct 66 ms 15644 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 4 ms 9784 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9816 KB Output is correct
5 Correct 4 ms 10072 KB Output is correct
6 Correct 7 ms 10296 KB Output is correct
7 Correct 66 ms 15700 KB Output is correct
8 Correct 5 ms 10072 KB Output is correct
9 Correct 6 ms 10188 KB Output is correct
10 Correct 70 ms 15544 KB Output is correct
11 Correct 63 ms 15700 KB Output is correct
12 Correct 103 ms 15800 KB Output is correct
13 Correct 66 ms 15644 KB Output is correct
14 Correct 114 ms 21048 KB Output is correct
15 Correct 973 ms 89940 KB Output is correct
16 Correct 114 ms 21068 KB Output is correct
17 Correct 973 ms 89928 KB Output is correct
18 Correct 552 ms 102480 KB Output is correct
19 Correct 566 ms 90440 KB Output is correct
20 Correct 724 ms 89716 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 98 ms 14672 KB Output is correct
4 Correct 645 ms 96652 KB Output is correct
5 Correct 859 ms 92152 KB Output is correct
6 Correct 984 ms 89912 KB Output is correct
7 Correct 1027 ms 88660 KB Output is correct
8 Correct 1112 ms 88036 KB Output is correct
9 Correct 718 ms 92232 KB Output is correct
10 Correct 736 ms 91500 KB Output is correct
11 Correct 563 ms 114000 KB Output is correct
12 Correct 666 ms 88816 KB Output is correct
13 Correct 602 ms 105812 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 5 ms 10076 KB Output is correct
7 Correct 16 ms 10588 KB Output is correct
8 Correct 23 ms 10648 KB Output is correct
9 Correct 20 ms 10588 KB Output is correct
10 Correct 14 ms 10660 KB Output is correct
11 Correct 16 ms 10588 KB Output is correct
12 Correct 16 ms 10588 KB Output is correct
13 Correct 19 ms 10588 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9896 KB Output is correct
4 Correct 5 ms 9952 KB Output is correct
5 Correct 6 ms 10276 KB Output is correct
6 Correct 594 ms 88740 KB Output is correct
7 Correct 901 ms 88656 KB Output is correct
8 Correct 1112 ms 88716 KB Output is correct
9 Correct 915 ms 88144 KB Output is correct
10 Correct 544 ms 91988 KB Output is correct
11 Correct 568 ms 89428 KB Output is correct
12 Correct 481 ms 96336 KB Output is correct
13 Correct 574 ms 90448 KB Output is correct
14 Correct 803 ms 88912 KB Output is correct
15 Correct 1000 ms 88820 KB Output is correct
16 Correct 465 ms 92244 KB Output is correct
17 Correct 512 ms 89432 KB Output is correct

Subtask #7
25.0 / 25.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 3 ms 9832 KB Output is correct
4 Correct 5 ms 9952 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 48 ms 13600 KB Output is correct
7 Correct 98 ms 21428 KB Output is correct
8 Correct 453 ms 91476 KB Output is correct
9 Correct 436 ms 91444 KB Output is correct
10 Correct 467 ms 91988 KB Output is correct
11 Correct 487 ms 95824 KB Output is correct
12 Correct 503 ms 104528 KB Output is correct
13 Correct 533 ms 116400 KB Output is correct
14 Correct 539 ms 90628 KB Output is correct
15 Correct 5 ms 9816 KB Output is correct
16 Correct 4 ms 9784 KB Output is correct
17 Correct 4 ms 9820 KB Output is correct
18 Correct 5 ms 9816 KB Output is correct
19 Correct 4 ms 10072 KB Output is correct
20 Correct 7 ms 10296 KB Output is correct
21 Correct 66 ms 15700 KB Output is correct
22 Correct 5 ms 10072 KB Output is correct
23 Correct 6 ms 10188 KB Output is correct
24 Correct 70 ms 15544 KB Output is correct
25 Correct 63 ms 15700 KB Output is correct
26 Correct 103 ms 15800 KB Output is correct
27 Correct 66 ms 15644 KB Output is correct
28 Correct 114 ms 21048 KB Output is correct
29 Correct 973 ms 89940 KB Output is correct
30 Correct 114 ms 21068 KB Output is correct
31 Correct 973 ms 89928 KB Output is correct
32 Correct 552 ms 102480 KB Output is correct
33 Correct 566 ms 90440 KB Output is correct
34 Correct 724 ms 89716 KB Output is correct
35 Correct 5 ms 9820 KB Output is correct
36 Correct 4 ms 9820 KB Output is correct
37 Correct 98 ms 14672 KB Output is correct
38 Correct 645 ms 96652 KB Output is correct
39 Correct 859 ms 92152 KB Output is correct
40 Correct 984 ms 89912 KB Output is correct
41 Correct 1027 ms 88660 KB Output is correct
42 Correct 1112 ms 88036 KB Output is correct
43 Correct 718 ms 92232 KB Output is correct
44 Correct 736 ms 91500 KB Output is correct
45 Correct 563 ms 114000 KB Output is correct
46 Correct 666 ms 88816 KB Output is correct
47 Correct 602 ms 105812 KB Output is correct
48 Correct 4 ms 9820 KB Output is correct
49 Correct 4 ms 9820 KB Output is correct
50 Correct 3 ms 9820 KB Output is correct
51 Correct 3 ms 9820 KB Output is correct
52 Correct 4 ms 9820 KB Output is correct
53 Correct 5 ms 10076 KB Output is correct
54 Correct 16 ms 10588 KB Output is correct
55 Correct 23 ms 10648 KB Output is correct
56 Correct 20 ms 10588 KB Output is correct
57 Correct 14 ms 10660 KB Output is correct
58 Correct 16 ms 10588 KB Output is correct
59 Correct 16 ms 10588 KB Output is correct
60 Correct 19 ms 10588 KB Output is correct
61 Correct 68 ms 13204 KB Output is correct
62 Correct 109 ms 19540 KB Output is correct
63 Correct 513 ms 88660 KB Output is correct
64 Correct 674 ms 88660 KB Output is correct
65 Correct 883 ms 88768 KB Output is correct
66 Correct 1057 ms 88660 KB Output is correct
67 Correct 976 ms 88040 KB Output is correct
68 Correct 587 ms 92716 KB Output is correct
69 Correct 696 ms 89424 KB Output is correct
70 Correct 578 ms 95824 KB Output is correct
71 Correct 728 ms 90288 KB Output is correct
72 Correct 952 ms 88916 KB Output is correct
73 Correct 1094 ms 88660 KB Output is correct
74 Correct 537 ms 88656 KB Output is correct
75 Correct 617 ms 89552 KB Output is correct