## 11898 - Killer Problem

Moderator: Board moderators

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

### 11898 - Killer Problem

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

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

) 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

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

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

i use insertion sort + binary search in STL vector. My runtime is 0.568s
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

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