Guest User

Untitled

a guest
Oct 15th, 2013
2,889
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. #define M_S 1000
  5. int comp(const void* a,const void *b){
  6.     int *A=(*(int**)a);
  7.     int *B=(*(int**)b);
  8.     if(A[0]!=B[0])return A[0]-B[0];
  9.     return A[1]-B[1];
  10. }
  11. int **arr;
  12. int arr2[100005];
  13. int n,m;
  14. int pree[110][100005];
  15. int deg[110]={0};
  16. int main(){
  17.     cin>>n>>m;
  18.     arr=new int*[n+1];
  19.     for(int i=1;i<=n;i++){
  20.         arr[i]=new int[2];
  21.         cin>>arr[i][0];
  22.         arr[i][1]=i;
  23.         arr2[i]=arr[i][0];
  24.     }
  25.     qsort(arr+1,n,sizeof(int),comp);
  26.    
  27.     for(int i=0;i<110;i++){
  28.         for(int e=0;e<100005;e++){
  29.             pree[i][e]=0;
  30.         }
  31.     }
  32.     for(int i=1;i<=n;i++){
  33.         pree[(i-1)/M_S][arr[i][1]]=1;
  34.     }
  35.     for(int i=0;i<110;i++){
  36.         for(int e=1;e<=n;e++){
  37.             pree[i][e]+=pree[i][e-1];
  38.         }
  39.     }
  40.     int a,b,k,tmp;
  41.     while(m--){
  42.         tmp=0;
  43.         cin>>a>>b>>k;
  44.         for(int i=0;i<110;i++){
  45.             if(tmp+pree[i][b]-pree[i][a-1]>=k){
  46.                 for(int e=i*M_S;e<(i+1)*M_S && e<=n;e++){
  47.                     if(arr[e+1][1]>=a && arr[e+1][1]<=b){
  48.                         tmp++;
  49.                     }
  50.                     if(tmp==k){
  51.                         cout<<arr2[arr[e+1][1]]<<endl;
  52.                         break;
  53.                     }
  54.                 }
  55.                 break;
  56.             } else {
  57.                 tmp+=pree[i][b]-pree[i][a-1];
  58.             }
  59.         }
  60.     }
  61. }
RAW Paste Data