oj.uz

Submission #1013190

# Submission time Handle Problem Language Result Execution time Memory
1013190 2024-07-03T09:32:52 Z boris_mihov Comparing Plants (IOI20_plants) C++17
44 / 100
 355 ms 43092 KB 
#include "plants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
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);
    }
};

SegmentTree tree;
int r[MAXN];
int h[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);
}

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);
    }
}

int compare_plants(int x, int y) 
{
	x++; y++;
    if (h[x] > h[y]) return 1;
    return -1;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Incorrect 3 ms 11100 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 3 ms 11100 KB Output is correct
2 Correct 3 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11352 KB Output is correct
7 Correct 39 ms 16000 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 4 ms 11356 KB Output is correct
10 Correct 39 ms 15868 KB Output is correct
11 Correct 39 ms 16212 KB Output is correct
12 Correct 36 ms 16048 KB Output is correct
13 Correct 39 ms 15952 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11100 KB Output is correct
2 Correct 3 ms 11100 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11352 KB Output is correct
7 Correct 39 ms 16000 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 4 ms 11356 KB Output is correct
10 Correct 39 ms 15868 KB Output is correct
11 Correct 39 ms 16212 KB Output is correct
12 Correct 36 ms 16048 KB Output is correct
13 Correct 39 ms 15952 KB Output is correct
14 Correct 78 ms 16548 KB Output is correct
15 Correct 355 ms 19028 KB Output is correct
16 Correct 57 ms 16300 KB Output is correct
17 Correct 319 ms 19104 KB Output is correct
18 Correct 231 ms 31016 KB Output is correct
19 Correct 196 ms 18932 KB Output is correct
20 Correct 268 ms 18976 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 44 ms 15892 KB Output is correct
4 Correct 156 ms 24372 KB Output is correct
5 Correct 201 ms 19696 KB Output is correct
6 Correct 251 ms 18772 KB Output is correct
7 Correct 282 ms 18616 KB Output is correct
8 Correct 306 ms 18904 KB Output is correct
9 Correct 207 ms 21584 KB Output is correct
10 Correct 177 ms 20748 KB Output is correct
11 Correct 148 ms 43092 KB Output is correct
12 Correct 154 ms 18512 KB Output is correct
13 Correct 223 ms 35920 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11096 KB Output is correct
2 Correct 5 ms 11236 KB Output is correct
3 Incorrect 2 ms 11232 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 11096 KB Output is correct
2 Correct 2 ms 11100 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Incorrect 3 ms 11100 KB Output isn't correct
5 Halted 0 ms 0 KB -