oj.uz

Submission #781886

# Submission time Handle Problem Language Result Execution time Memory
781886 2023-07-13T12:40:07 Z boris_mihov Comparing Plants (IOI20_plants) C++17
27 / 100
 270 ms 134832 KB 
#include "plants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2000000 + 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 48 ms 125516 KB Output is correct
2 Correct 48 ms 125508 KB Output is correct
3 Correct 56 ms 125468 KB Output is correct
4 Incorrect 48 ms 125532 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 47 ms 125436 KB Output is correct
2 Correct 47 ms 125504 KB Output is correct
3 Correct 47 ms 125532 KB Output is correct
4 Correct 49 ms 125424 KB Output is correct
5 Correct 56 ms 125468 KB Output is correct
6 Correct 50 ms 125648 KB Output is correct
7 Correct 99 ms 128432 KB Output is correct
8 Correct 58 ms 125520 KB Output is correct
9 Correct 50 ms 125516 KB Output is correct
10 Correct 90 ms 128436 KB Output is correct
11 Correct 94 ms 128340 KB Output is correct
12 Correct 88 ms 128532 KB Output is correct
13 Correct 91 ms 128384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 125436 KB Output is correct
2 Correct 47 ms 125504 KB Output is correct
3 Correct 47 ms 125532 KB Output is correct
4 Correct 49 ms 125424 KB Output is correct
5 Correct 56 ms 125468 KB Output is correct
6 Correct 50 ms 125648 KB Output is correct
7 Correct 99 ms 128432 KB Output is correct
8 Correct 58 ms 125520 KB Output is correct
9 Correct 50 ms 125516 KB Output is correct
10 Correct 90 ms 128436 KB Output is correct
11 Correct 94 ms 128340 KB Output is correct
12 Correct 88 ms 128532 KB Output is correct
13 Correct 91 ms 128384 KB Output is correct
14 Correct 102 ms 128620 KB Output is correct
15 Correct 259 ms 131044 KB Output is correct
16 Correct 102 ms 130940 KB Output is correct
17 Correct 270 ms 134832 KB Output is correct
18 Correct 202 ms 134276 KB Output is correct
19 Correct 195 ms 134768 KB Output is correct
20 Correct 234 ms 134832 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 125436 KB Output is correct
2 Correct 48 ms 125464 KB Output is correct
3 Incorrect 89 ms 128368 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125456 KB Output is correct
2 Correct 49 ms 125468 KB Output is correct
3 Incorrect 50 ms 125420 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 48 ms 125508 KB Output is correct
3 Correct 56 ms 125468 KB Output is correct
4 Incorrect 48 ms 125532 KB Output isn't correct
5 Halted 0 ms 0 KB -