I wrote 2 different codes and both failed the sixth Test. Please, help me!
---------------------------------------------------------------------------------------
Code #1 (BinaryTree):

using System;
using System.Collections.Generic;

namespace ConsoleApp35
{
    class Program
    {
        class TreeNode
        {
            public TreeNode left { get; set; }
            public TreeNode right { get; set; }
            public uint data1;
            public int data2;
        }

        class BinaryTree
        {
            public TreeNode root = null;

            public void AddRoot(uint data1, int data2)
            {
                TreeNode n = new TreeNode();
                n.data1 = data1;
                n.data2 = data2;
                root = n;
                return;
            }

            public void Add(uint data1, int data2)
            {
                TreeNode n = new TreeNode();
                n.data1 = data1;
                n.data2 = data2;
                TreeNode current = root;

                while (true)
                {
                    if (n.data1 < current.data1)
                    {
                        if (current.left == null)
                        {
                            current.left = n;
                            return;
                        }
                        else
                            current = current.left;
                    }
                    else
                    {
                        if (current.right == null)
                        {
                            current.right = n;
                            return;
                        }
                        else
                            current = current.right;
                    }
                }
            }

            public TreeNode Search(uint data1, TreeNode node)
            {
                if (node == null) return null;
                else if (node.data1 == data1) return node;
                else if (data1 < node.data1)
                    return Search(data1, node.left);
                else
                    return Search(data1, node.right);
            }

            public TreeNode ModifySearch(uint data1, TreeNode node, uint l, uint r)
            {
                if (node == null) return null;
                else if (node.data1 == data1 && node.data2 >= l && node.data2 <= r) return node;
                else if (data1 < node.data1)
                    return ModifySearch(data1, node.left, l, r);
                else
                    return ModifySearch(data1, node.right, l, r);
            }
        }

        static void Main(string[] args)
        {
            BinaryTree BT = new BinaryTree();

            int n = int.Parse(Console.ReadLine());
            var s = Console.ReadLine().Split();
            BT.AddRoot(uint.Parse(s[0]), 1);
            for (int i = 1; i < n; i++)
                BT.Add(uint.Parse(s[i]), i+1);

            int q = int.Parse(Console.ReadLine());

            uint[,] lrx = new uint[q, 3];
            string res = "";

            for (int i = 0; i < q; i++)
            {
                s = Console.ReadLine().Split();
                lrx[i, 0] = uint.Parse(s[0]);
                lrx[i, 1] = uint.Parse(s[1]);
                lrx[i, 2] = uint.Parse(s[2]);

                TreeNode a = BT.ModifySearch(lrx[i, 2], BT.root, lrx[i, 0], lrx[i, 1]);
                if (a == null) res += '0';
                else res += '1';
            }
            Console.WriteLine(res);
        }
    }
}

---------------------------------------------------------------------------------------

Code #2 (QuickSort + BinarySearch):

using System;

namespace ConsoleApp34
{
    class Program
    {
        public static int Partition(ref int[] a, int down, int up)
        {
            int pivot = a[down];
            int index = down;
            int i = down + 1, j = up;
            while (true)
            {
                while (a[i] <= pivot && i <= up - 1) i++;
                while (a[j] >= pivot && j >= down + 1) j--;
                if (i >= j)
                {
                    int tmp = a[index];
                    a[index] = a[j];
                    a[j] = tmp;
                    return j;
                }
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++; j--;
            }
        }

        public static void QuickSort(ref int[] a, int down, int up)
        {
            if (down < up)
            {
                int p = Partition(ref a, down, up);
                QuickSort(ref a, down, p - 1);
                QuickSort(ref a, p + 1, up);
            }
        }

        public static int BS(int[] a, int key)
        {
            int l = 0;
            int r = a.Length - 1;
            while (l < r - 1)
            {
                int m = l + (r - l) / 2;
                if (a[m] < key)
                    l = m;
                else
                    r = m;
            }
            if (a[l].CompareTo(key) == 0)
                return l;
            if (a[r].CompareTo(key) == 0)
                return r;
            return -1;
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] a = new int[n];
            int[] a_copy = new int[n];
            int[] keys = new int[n];

            var s = Console.ReadLine().Split();
            for (int i = 0; i < n; i++)
            {
                a[i] = int.Parse(s[i]);
                a_copy[i] = int.Parse(s[i]);
            }

            QuickSort(ref a,0,a.Length-1);

            for (int i = 0; i < a.Length; i++)
                for (int j = 0; j < a.Length; j++)
                {
                    if (a[i] == a_copy[j])
                    {
                        keys[i] = j + 1;
                        a_copy[j] = -1;
                        break;
                    }
                }

            int q = int.Parse(Console.ReadLine());
            int[] l = new int[q];
            int[] r = new int[q];
            int[] x = new int[q];
            string res = "";

            for (int i = 0; i < q; i++)
            {
                s = Console.ReadLine().Split();
                l[i] = int.Parse(s[0]);
                r[i] = int.Parse(s[1]);
                x[i] = int.Parse(s[2]);

                int index = BS(a, x[i]);
                int j = index;
                bool b = false;
                while (j >= 0 && j < a.Length && a[j] == a[index])
                {
                    int realPlace = keys[j++];
                    if (realPlace <= r[i] && realPlace >= l[i])
                    {
                        res += '1'; b = true; break;
                    }
                }
                if (!b) res += '0';

            }
            Console.WriteLine(res);
        }
    }
}

Edited by author 29.03.2019 19:45

The improved second code also fails the sixth test (TLE).

using System;
using System.Collections.Generic;
namespace ConsoleApp34
{
    class Node
    {
        public int data1;
        public int data2;
    }

    class Program
    {
        public static int modifyPartition(ref Node[] a, int down, int up)
        {
            int pivot = a[down].data1;
            int index = down;
            int i = down + 1, j = up;
            while (true)
            {
                while (a[i].data1 <= pivot && i <= up - 1) i++;
                while (a[j].data1 >= pivot && j >= down + 1) j--;
                if (i >= j)
                {
                    int tmp1 = a[index].data1;
                    int tmp2 = a[index].data2;
                    a[index].data1 = a[j].data1;
                    a[index].data2 = a[j].data2;
                    a[j].data1 = tmp1;
                    a[j].data2 = tmp2;
                    return j;
                }
                int temp1 = a[i].data1;
                int temp2 = a[i].data2;
                a[i].data1 = a[j].data1;
                a[i].data2 = a[j].data2;
                a[j].data1 = temp1;
                a[j].data2 = temp2;
                i++; j--;
            }
        }

        public static void modifyQS(ref Node[] a, int down, int up)
        {
            if (down < up)
            {
                int p = modifyPartition(ref a, down, up);
                modifyQS(ref a, down, p - 1);
                modifyQS(ref a, p + 1, up);
            }
        }

        public static int modifyBS(Node[] a, int key)
        {
            int l = 0;
            int r = a.Length - 1;
            while (l < r - 1)
            {
                int m = l + (r - l) / 2;
                if (a[m].data1 < key)
                    l = m;
                else
                    r = m;
            }

            if (a[l].data1.CompareTo(key) == 0)
                return l;
            if (a[r].data1.CompareTo(key) == 0)
                return r;
            return -1;
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            Node[] info = new Node[n];

            var s = Console.ReadLine().Split();
            for (int i = 0; i < n; i++)
            {
                info[i] = new Node();
                info[i].data1 = int.Parse(s[i]);
                info[i].data2 = i+1;
            }

            modifyQS(ref info, 0, info.Length - 1);

            int q = int.Parse(Console.ReadLine());
            int[] l = new int[q];
            int[] r = new int[q];
            int[] x = new int[q];
            string res = "";

            for (int i = 0; i < q; i++)
            {
                s = Console.ReadLine().Split();
                l[i] = int.Parse(s[0]);
                r[i] = int.Parse(s[1]);
                x[i] = int.Parse(s[2]);

                int index = modifyBS(info, x[i]);
                int j = index;
                bool b = false;
                while (j >= 0 && j < info.Length && info[j].data1 == info[index].data1)
                {
                    if (info[j].data2 <= r[i] && info[j].data2 >= l[i])
                    {
                        res += '1';
                        b = true;
                        break;
                    }
                    j++;
                }
                if (!b) res += '0';

            }
            Console.WriteLine(res);
        }
    }
}