oj.uz

Submission #781887

# Submission time Handle Problem Language Result Execution time Memory
781887 2023-07-13T12:40:53 Z boris_mihov Comparing Plants (IOI20_plants) C++17
14 / 100
 63 ms 35600 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)
        {
            assert(2*node + 1 < 4*MAXN);
            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 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Incorrect 5 ms 12756 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 12788 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Correct 6 ms 12836 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 47 ms 15728 KB Output is correct
8 Correct 6 ms 12884 KB Output is correct
9 Correct 7 ms 12904 KB Output is correct
10 Correct 56 ms 15732 KB Output is correct
11 Correct 55 ms 15644 KB Output is correct
12 Correct 45 ms 15780 KB Output is correct
13 Correct 46 ms 15692 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12788 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 5 ms 12756 KB Output is correct
5 Correct 6 ms 12836 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 47 ms 15728 KB Output is correct
8 Correct 6 ms 12884 KB Output is correct
9 Correct 7 ms 12904 KB Output is correct
10 Correct 56 ms 15732 KB Output is correct
11 Correct 55 ms 15644 KB Output is correct
12 Correct 45 ms 15780 KB Output is correct
13 Correct 46 ms 15692 KB Output is correct
14 Correct 60 ms 15876 KB Output is correct
15 Runtime error 63 ms 35600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 44 ms 15564 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 5 ms 12756 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Incorrect 5 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 5 ms 12756 KB Output is correct
3 Correct 5 ms 12756 KB Output is correct
4 Incorrect 5 ms 12756 KB Output isn't correct
5 Halted 0 ms 0 KB -