oj.uz

Submission #781880

# Submission time Handle Problem Language Result Execution time Memory
781880 2023-07-13T12:36:42 Z boris_mihov Comparing Plants (IOI20_plants) C++17
0 / 100
 48 ms 15576 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
        {
            update(1, n, 1, 1, idx - 1);
            update(1, n, 1, n - (k - idx), 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;

int getPrev(int idx)
{
    if (idx == 1) return n;
    return idx - 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];
    }

    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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 5 ms 12748 KB Output is correct
4 Incorrect 6 ms 12756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12752 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Incorrect 48 ms 15576 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 5 ms 12772 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 12732 KB Output is correct
2 Correct 6 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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 5 ms 12748 KB Output is correct
4 Incorrect 6 ms 12756 KB Output isn't correct
5 Halted 0 ms 0 KB -