oj.uz

Submission #781882

# Submission time Handle Problem Language Result Execution time Memory
781882 2023-07-13T12:38:22 Z boris_mihov Comparing Plants (IOI20_plants) C++17
14 / 100
 65 ms 35544 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) + 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;

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 12776 KB Output is correct
3 Correct 6 ms 12768 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 6 ms 12796 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12832 KB Output is correct
5 Correct 6 ms 12756 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 59 ms 15760 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 45 ms 15704 KB Output is correct
11 Correct 44 ms 15592 KB Output is correct
12 Correct 45 ms 15820 KB Output is correct
13 Correct 47 ms 15676 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12796 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Correct 6 ms 12756 KB Output is correct
4 Correct 6 ms 12832 KB Output is correct
5 Correct 6 ms 12756 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 59 ms 15760 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 45 ms 15704 KB Output is correct
11 Correct 44 ms 15592 KB Output is correct
12 Correct 45 ms 15820 KB Output is correct
13 Correct 47 ms 15676 KB Output is correct
14 Correct 58 ms 15996 KB Output is correct
15 Runtime error 65 ms 35544 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 6 ms 12804 KB Output is correct
2 Correct 5 ms 12756 KB Output is correct
3 Incorrect 43 ms 15580 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 5 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 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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12776 KB Output is correct
3 Correct 6 ms 12768 KB Output is correct
4 Incorrect 5 ms 12756 KB Output isn't correct
5 Halted 0 ms 0 KB -