11898 - Killer Problem

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11898 - Killer Problem

Post by Angeh » Sun Oct 31, 2010 10:42 am

HI experts ...
whats The Idea To solve this problem ...
i'm tired of thinking so much ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11898 - Killer Problem

Post by Leonid » Mon Nov 01, 2010 11:01 am

That looks like a Range Minimal Query problem.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11898 - Killer Problem

Post by Angeh » Mon Nov 01, 2010 4:56 pm

:)) solved it ... much more easier problem ... than what i was thinking ... lol ... :))
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Mizanur Rahman(IUK)
New poster
Posts: 12
Joined: Wed Aug 18, 2010 12:07 pm

Re: 11898 - Killer Problem

Post by Mizanur Rahman(IUK) » Mon Nov 01, 2010 6:26 pm

TLE Please help me

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int t,i;
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		long int n,tmp,q,j,k;
		//long int  v[200000],k;
		vector<long int > v,p;
	//	vector<long int >::iterator l;
		scanf("%ld",&n);
		for( j=0;j<n;j++)
		{scanf("%d",&q);v.push_back(q);}
		scanf("%ld",&q);
		for(j=0;j<q;j++)
		{
			long int a,b;
			scanf("%ld%ld",&a,&b);
			for(k=a-1;k<b;k++)
				p.push_back(v[k]);
			sort(p.begin(),p.end());
			printf("%ld\n",p[1]-p[0]);
			p.clear();	
		}
	}
	return 0;
}

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11898 - Killer Problem

Post by Angeh » Mon Nov 01, 2010 6:30 pm

vector will Time out ...
think whats The answer for the Quary 2-20000?????
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

yan yan
New poster
Posts: 13
Joined: Thu May 13, 2010 4:16 pm
Location: Viet Nam
Contact:

Re: 11898 - Killer Problem

Post by yan yan » Mon Apr 18, 2011 2:51 am

i use insertion sort + binary search in STL vector. My runtime is 0.568s :D
p.s: how to use RMQ to solve this problem :-?

shaon81
New poster
Posts: 1
Joined: Sun Oct 23, 2011 7:26 pm

Re: 11898 - Killer Problem

Post by shaon81 » Sun Oct 23, 2011 7:32 pm

This problem can be solved by simple modification of counting sort and observation. because numbers range is small. :)

Post Reply

Return to “Volume 118 (11800-11899)”