501 - Black Box

[x140l31]

I don't know if your algorithm is correct, I'm no C++ guy.

The problem as I implemented it: with each "ADD" query add the number to your data structure. With the i-th "GET" query print the i-th smallest number in the data structure.

The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.

EDIT: I tried this input's and I get correct answers...

I use a balanced AVL

Code: Select all

#include <iostream>
using namespace std;

class AVL
{
    private:
        struct Node
        {
            int val;
            Node* nleft;
            Node* nright;
            int hei;
            int num;

            Node(int v, Node* fe, Node* fd, int a, int n)
                :   val(v), nleft(fe), nright(fd), hei(a), num(n)
            { }
        };

        Node* arrel;

    public:
        AVL()
        {
            arrel = NULL;
        }

        void insert(int n)
        {
            insert(arrel, n);
        }

        int search(int x)
        {
            search(arrel, x);
        }

    private:
        static int height(Node* p)
        {
            return p ? p->hei : -1;
        }

        static int number(Node* p)
        {
            return p ? p->num : 0;
        }

        static void update(Node* p)
        {
            p->hei = 1 + max(height(p->nleft), height(p->nright));
            p->num = 1 + number(p->nleft) + number(p->nright);
        }

        static void LL(Node*& p)
        {
            Node* q = p;
            p = p->nleft;
            q->nleft = p->nright;
            p->nright = q;
            update(q);
            update(p);
        }

        static void RR(Node*& p)
        {
            Node* q = p;
            p = p->nright;
            q->nright = p->nleft;
            p->nleft = q;
            update(q);
            update(p);
        }

        static void LR(Node*& p)
        {
            RR(p->nleft);
            LL(p);
        }

        static void RL(Node*& p)
        {
            LL(p->nright);
            RR(p);
        }

        void balanceLeft(Node*& p)
        {
            if(height(p->nright) - height(p->nleft)==2)
            {
                if(height(p->nright->nleft) - height(p->nright->nright) == 1) RL(p);
                else RR(p);
            }
            else update(p);
        }

        void balanceRight(Node*& p)
        {
            if(height(p->nleft) - height(p->nright) == 2)
            {
                if(height(p->nleft->nright) - height(p->nleft->nleft) == 1) LR(p);
                else LL(p);
            }
            else update(p);
        }

        void insert(Node*& p, int val)
        {
            if(p)
            {
                if(val <= p->val)
                {
                    insert(p->nleft, val);
                    if(height(p->nleft) - height(p->nright) == 2)
                    {
                        if(val <= p->nleft->val) LL(p);
                        else LR(p);
                    }
                    update(p);
                }
                else
                {
                    insert(p->nright, val);
                    if(height(p->nright) - height(p->nleft) == 2)
                    {
                        if(val > p->nright->val) RR(p);
                        else RL(p);
                    }
                    update(p);
                }
            }
            else p = new Node(val, 0, 0, 0, 1);
        }

        int search(Node* p, int x)
        {
            int aux = number(p) - number(p->nright);
            if (x == aux) return p->val;
            if(x > aux) return search(p->nright, x - aux);
            return search(p->nleft, x);
        }
};

int main()
{
    int k, n, m;
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d %d", &m, &n);
        int A[m], u, ins = 0;
        AVL T;
        for (int i = 0; i < m; ++i) scanf("%d", &A[i]);
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &u);
            while (ins != u) { T.insert(A[ins]); ++ins; }
            printf("%d\n", T.search(i + 1));
        }
        if (k) printf("\n");
    }
}

[uDebug]

You can definitely solve this problem with C++ STL multiset in less than 1 second. So if you still get TLE, most likely each time you do a GET, you are resetting your iterator to the beginning of your multiset and incrementing it one by one until you arrive at the proper position. This will take way too long. You should instead remember your iterator's position, and manipulate it accordingly when new elements are inserted to your multiset. To be precise, you need to decrement it when you are inserting an element that's smaller than what your iterator is pointing to.

To answer Fernando's question, the hint is to not instantly increment the iterator after you do a GET operation. In other words, after you do a GET, leave you iterator alone. Then decrement the iterator each time you are inserting a new element that's strictly smaller than what your iterator is currently pointing to. Then when it's finally time for another GET operation, now do the iterator increment.

This was some amazing insight! Thanks so much for sharing. It really helped me optimize my program and see an an amazing idea in action.

Here's some input / output that helped during testing / debugging. Note that the second test case was culled from an earlier post in the forums and credit goes to the OP, rio.

Also, note that in the output, there's a blank line only in between data sets. So, there's no blank line after the last output.

Input:

Code: Select all

4

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

9 5
1 -8 3 5 1 0 4 2 1
1 3 3 6 8

10 5
1 -2000000000 2000000000 999 82746 -12894 -88 32234 1212 -278
1 5 5 5 9

13 3
-468606385 388978246 -660049128 773379450 -6889397 -589131515 257901044 475125477 345048443 -78014404 -190001670 -218815409 525924744 
3 3 4 

AC Output:

Code: Select all

3
3
1
2

1
1
3
1
2

1
1
999
82746
999

-660049128
-468606385
388978246

[longted]

can tell me why is TLE.how to Solve TLE program

Code: Select all

#include<stdio.h>
#include<set>

using namespace std;
#define MAX_SIZE 20000
int main()
{
	int case_count=0;
	scanf("%d",&case_count);
	while(case_count--)
	{
		set<int> my_set[MAX_SIZE];
		int my_set_count=1;
		int m=0,n=0,get_command=0;
		scanf("%d %d",&m,&n);
		for(int i=1;i<=m;i++)
		{
			int data=0;
			scanf("%d",&data);
			if(i==1)
				my_set[my_set_count++].insert(data);
			else
			{
				set<int> tmp;
				tmp.insert(data);
				for(int i=1;i<=my_set_count;i++)
				{
					set<int>::iterator it;
					for(it=my_set[i].begin();it!=my_set[i].end();++it)
					{
						int get_data=*it;
						tmp.insert(get_data);
					}
				}
				my_set[my_set_count++]=tmp;
			}
		
		}
/*		for(int i=1;i<=my_set_count;i++)
		{
			set<int> tmp=my_set[i];
			set<int>::iterator it;
			for(it=tmp.begin();it!=tmp.end();it++)
			{
					printf("%d ",*it);
			}
			printf("\n");
		}
*/
		int orders=1;
		for(int i=0;i<n;i++)
		{
			scanf("%d",&get_command);
			set<int> tmp=my_set[get_command];
			set<int>::iterator it;
			int count=0;
			for(it=tmp.begin();it!=tmp.end();++it)
			{
				count++;
				if(orders==count)
				{
					orders++;
					printf("%d\n",*it);
					break;
				}
			}
		}
		if(case_count>0)
			printf("\n");
	
	
	
	}
	return 0;
}

[brianfry713]

Read this thread.

[Mukit Chowdhury]

So this problem can't be solved using java Collection.

[Zakoshnon]

Precautional measures to concentrate hazard in the representative of toxic chemicals much as decolourize permit victimization diluent bleaches to concentrate the absorption. Observe your hole anxiety pro for a rumbling sensation introspection leastwise erst every deuce period. Canvin JR, Marvin AP, Sivakumaran M, et al purchase line forzest erectile dysfunction protocol amino acids.
I emotion the thought of supplements as well: if you drop right, you don't necessary supplements! When we definite to maintenance for our bodies as they should be stolen tutelage of, we so are treating them as the temples of the animate that they are. They are your friends, but not your debase purchase cialis jelly 20mg with amex erectile dysfunction best pills. Abaft all, when you development ninety, you scarce hawthorn comfort indigence those aching knees! If you acquire inclined a victuals and your formula calls for a astronomic assignation size, chilling substance that you instrument not function opportune by alternatively of gobbling it up. This is because bread is undischarged with calories purchase discount sildalis on-line impotence type 1 diabetes. Workers at thousands of sites cogitate autonomous and secret Investigation and administer alive content. You'll shortly see condition in the portion you flavor and feel, and that instrument amend you examine forrader to your day-to-day practise. -- Bone Dig Syndrome cheap malegra dxt generic erectile dysfunction questions to ask.
No figure still knows precisely how EPA works, but it is believed to decrease inflammation, wiry the blood, addition 5-hydroxytryptamine levels, and better descent feed to the brainpower star to greater inter-connectivity in the neuronic networks. In the firs 3 4 life the symptoms are almost intense, but the limit drops to meet 1 inside 20 life. Of teaching it does order xenical toronto weight loss ky. Thither are certain symptoms of hypothyroidism, which refer fatigue, lightheadedness and temper. Herbs are besides misused in poultices, and to soak clean or heater which is inaudible by the longanimous. Yee, A M, S C Ng, R E Sobel, and J E river 1997 order nizagara 100 mg erectile dysfunction neurological causes. What the md advisable was to turn fetching unforesightful 10 second walks, 2-3 nowadays a period rather of disagreeable to compressing in an distance walking former during the grade of the period. Faculty sparkle is likewise utilized for mattress toppers and wheelchair cushions and in over-the-counter situations where thither is a try of insistence sores. The children at maximal try for grippe complications are infants below 6 months buy cheap penegra 100mg on-line prostate oncology quality.
Evaporation has always deemed a curve by the lucullan as a life-style with added substances specified as steroid and cocain. And in the Thrombosis Arteria Endangerment Employment in Animal Adults Study, justified though trends were unswerving crossways cardinal geezerhood of review studies, age-related weighting profit was large in the archean to mid-20s than it was for elder geezerhood groups. If you unsuccessful in the past, what prefabricated you hollow in order discount kamagra polo erectile dysfunction natural cures. We know finished each the woody acquisition for you, do your personal enquiry for yourself today. "Not practical," she aforementioned. "Welfare issues pertain everyone generic 100mg zenegra mastercard erectile dysfunction diabetes type 2 treatment. This clause for Patients of pulmonic hypertension is presented for informational purposes exclusive. There's no uncertainty virtually it, cleaning the national torso offers numerous benefits and improves eudaimonia and aliveness. Cerebral edema: 025'15 g/kg/dose IV > 30 min meldonium 250mg with amex treatment molluscum contagiosum.