oj.uz

Submission #781885

# Submission time Handle Problem Language Result Execution time Memory
781885 2023-07-13T12:39:32 Z boris_mihov Comparing Plants (IOI20_plants) C++17
14 / 100
 65 ms 35552 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  = 1e9;

int n, k;
struct SegmentTree
{
    struct Node
    {
        int max;
        int lazy;
        int leftPos;
        int rightPos;

        Node()
        {
            max = lazy = leftPos = rightPos = 0;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        if (left.max == right.max)
        {
            Node res;
            res.max = left.max;
            res.leftPos = left.leftPos;
            res.rightPos = right.rightPos;
            return res;
        }

        if (left.max > right.max)
        {
            return left;
        } else
        {
            return right;
        }
    }

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

        tree[node].max += 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 build(int l, int r, int node, int vals[])
    {
        if (l == r)
        {
            tree[node].max = vals[l];
            tree[node].leftPos = l;
            tree[node].rightPos = l;
            return;
        }

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

    void pointUpdate(int l, int r, int node, int queryPos)
    {
        push(node, l, r);
        if (queryPos < l || r < queryPos)
        {
            return;
        }

        if (l == r)
        {
            tree[node].max = -INF;
            return;
        }

        int mid = (l + r) / 2;
        pointUpdate(l, mid, 2*node, queryPos);
        pointUpdate(mid + 1 , r, 2*node + 1, queryPos);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

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

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

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR);
        update(mid + 1 , r, 2*node + 1, queryL, queryR);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    int findFirstEqual(int l, int r, int node, int queryPos, int max)
    {
        push(node, l, r);
        if (r < queryPos || tree[node].max < max)
        {
            return 0;
        }

        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        if (l >= queryPos)
        {
            push(2*node, l, r);
            if (tree[2*node].max == max) return findFirstEqual(l, mid, 2*node, queryPos, max);
            else return findFirstEqual(mid + 1, r, 2*node + 1, queryPos, max);
        }
    
        int res = findFirstEqual(l, mid, 2*node, queryPos, max);
        if (res != 0) return res;
        return findFirstEqual(mid + 1, r, 2*node + 1, queryPos, max);
    }

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

    void pointUpdate(int idx)
    {
        pointUpdate(1, n, 1, idx);
    }

    void update(int idx)
    {
        if (idx >= k)
        {
            update(1, n, 1, idx - k + 1, idx - 1);
        } else
        {
            if (idx > 1) update(1, n, 1, 1, idx - 1);
            update(1, n, 1, n - (k - idx) + 1, n);
        }
    }

    int findMAX()
    {
        if (tree[1].leftPos + k > tree[1].rightPos) return tree[1].leftPos;
        return findFirstEqual(1, n, 1, tree[1].leftPos + k, tree[1].max);
    }
};

int p[MAXN];
int r[MAXN];
SegmentTree tree;

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

    tree.build(r);
    for (int currTry = 1 ; currTry <= n ; ++currTry)
    {
        int max = tree.findMAX();
        p[max] = currTry;
        tree.pointUpdate(max);
        tree.update(max);
    }
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12756 KB Output is correct
2 Correct 6 ms 12832 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Incorrect 6 ms 12752 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 5 ms 12732 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 6 ms 12756 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 48 ms 15720 KB Output is correct
8 Correct 6 ms 12888 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 51 ms 15708 KB Output is correct
11 Correct 47 ms 15536 KB Output is correct
12 Correct 47 ms 15852 KB Output is correct
13 Correct 47 ms 15652 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12732 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Correct 6 ms 12756 KB Output is correct
5 Correct 6 ms 12756 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 48 ms 15720 KB Output is correct
8 Correct 6 ms 12888 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 51 ms 15708 KB Output is correct
11 Correct 47 ms 15536 KB Output is correct
12 Correct 47 ms 15852 KB Output is correct
13 Correct 47 ms 15652 KB Output is correct
14 Correct 60 ms 15888 KB Output is correct
15 Runtime error 65 ms 35552 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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