Cod sursa(job #2757910)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 7 iunie 2021 13:48:49
Problema Secv8 Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 6.03 kb
import java.io.*;
import java.util.Random;

class TreapNode
{
    TreapNode left;
    TreapNode right;
    int size;
    int priority;
    int value;
    boolean lazy;

    TreapNode(int value)
    {
        this.size = 1;
        this.value = value;
        this.priority = new Random().nextInt(1_000_000_000);
    }
}

class TreapNodePair
{
    TreapNode first;
    TreapNode second;

    TreapNodePair(TreapNode first, TreapNode second)
    {
        this.first = first;
        this.second = second;
    }
}

public class Treap {

    static TreapNode root;
    static OutputStream output;

    public static void update(TreapNode root)
    {
        if(root == null)
            return ;

        root.size = ((root.left == null) ? 0 : root.left.size) + ((root.right == null) ? 0 : root.right.size) + 1;
    }

    public static void propaga(TreapNode root)
    {
        if(root != null && root.lazy)
        {
            root.lazy = false;

            if(root.left != null)
                root.left.lazy = !root.left.lazy;

            if(root.right != null)
                root.right.lazy = !root.right.lazy;

            TreapNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

    public static TreapNode meld(TreapNode left, TreapNode right)
    {
        propaga(left);
        propaga(right);

        update(left);
        update(right);

        if(left == null)
            return right;

        if(right == null)
            return left;

        if(left.priority < right.priority)
        {
            left.right = meld(left.right, right);
            propaga(left);
            update(left);
            return left;
        }
        else
        {
            right.left = meld(left, right.left);
            propaga(right);
            update(right);
            return right;
        }
    }

    public static TreapNodePair split(TreapNode root, int key)
    {
        TreapNodePair res = new TreapNodePair(null, null);

        if(root == null)
            return res;

        propaga(root);
        update(root);

        int pos = 1;

        if(root.left != null)
            pos += root.left.size;

        if(pos == key)
        {
            res.first = root.left;
            root.left = null;
            res.second = root;
        }
        else if(pos < key)
        {
            TreapNodePair aux = split(root.right, key - pos);
            res.second = aux.second;
            root.right = aux.first;
            res.first = root;
        }
        else
        {
            TreapNodePair aux = split(root.left, key);
            res.first = aux.first;
            root.left = aux.second;
            res.second = root;
        }

        propaga(res.first);
        propaga(res.second);

        update(res.first);
        update(res.second);

        return res;
    }

    public static TreapNode insert(TreapNode root, int pos, int val)
    {
        propaga(root);
        update(root);

        TreapNodePair aux = split(root, pos);
        TreapNode solo = new TreapNode(val);

        return meld(meld(aux.first, solo), aux.second);
    }

    public static TreapNode reverse(TreapNode root, int x, int y)
    {
        propaga(root);
        update(root);

        TreapNodePair aux1 = split(root, y + 1);
        TreapNodePair aux2 = split(aux1.first, x);

        if(aux2.second != null)
            aux2.second.lazy = !aux2.second.lazy;

        return meld(meld(aux2.first, aux2.second), aux1.second);
    }

    public static TreapNode delete(TreapNode root, int x, int y)
    {
        propaga(root);
        update(root);

        TreapNodePair aux1 = split(root, y + 1);
        TreapNodePair aux2 = split(aux1.first, x);

        return meld(aux2.first, aux1.second);
    }

    public static int search(TreapNode root, int key)
    {
        if(root == null)
            return 0;

        propaga(root);
        update(root);

        int pos = 1;

        if(root.left != null)
            pos += root.left.size;

        if(key == pos)
            return root.value;

        if(key < pos)
            return search(root.left, key);
        else
            return search(root.right, key - pos);
    }

    public static void print(TreapNode root) throws IOException {
        if(root == null)
            return ;

        propaga(root);

        print(root.left);
        output.write((root.value + " ").getBytes());
        print(root.right);
    }

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("E:\\DS\\src\\com\\DS\\Treap\\secv8.in"));
        output = new BufferedOutputStream(new FileOutputStream("E:\\DS\\src\\com\\DS\\Treap\\secv8.out"));

        int numberOfOps = Integer.parseInt(br.readLine().split(" ")[0]);

        for(int i = 1; i <= numberOfOps; ++i)
        {
            String[] tmp = br.readLine().split(" ");
            char opType = tmp[0].charAt(0);

            switch(opType)
            {
                case 'I':
                    int pos = Integer.parseInt(tmp[1]);
                    int value = Integer.parseInt(tmp[2]);

                    root = insert(root, pos, value);
                    break;
                case 'A':
                    pos = Integer.parseInt(tmp[1]);
                    output.write((search(root, pos) + "\n").getBytes());
                    break;
                case 'R':
                    int x = Integer.parseInt(tmp[1]);
                    int y = Integer.parseInt(tmp[2]);
                    root = reverse(root, x, y);
                    break;
                default:
                    x = Integer.parseInt(tmp[1]);
                    y = Integer.parseInt(tmp[2]);
                    root = delete(root, x, y);
                    break;
            }
        }

        print(root);
        br.close();
        output.close();
    }
}