mihaimarcel21

median_query_60pct

Feb 20th, 2021
725
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define Long                    long long
  3. #define Ulong                   unsigned long long
  4. #define forn(i,n)               for( int i=0 ; i < n ; i++ )
  5. #define mp(i,j)                 make_pair(i,j)
  6. #define pb(a)                   push_back((a))
  7. #define all(x)                  (x).begin(),(x).end()
  8. #define gc                      getchar_unlocked
  9. #define PI                      acos(-1.0)
  10. #define EPS                     1e-9
  11. #define xx                      first
  12. #define yy                      second
  13. #define lc                      ((n)<<1)
  14. #define rc                      ((n)<<1|1)
  15. #define db(x)                   cout << #x << " -> " << x << endl;
  16. #define Di(x)                   int x;scanf("%d",&x)
  17. #define min(a,b)                ((a)>(b) ? (b) : (a) )
  18. #define max(a,b)                ((a)>(b) ? (a):(b))
  19. #define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
  20. #define N 100005
  21. using namespace std;
  22. ifstream fin("median_query.in");
  23. ofstream fout("median_query.out");
  24. int n,q;
  25. int a[N];
  26. vector<int>v;
  27. vector<int> seg[N*4];
  28. void build(int n,int b,int e)
  29. {
  30.     if(b==e){
  31.         seg[n].pb(a[b]);
  32.         return;
  33.     }
  34.     int mid = (b+e)/2;
  35.     build(lc,b,mid);
  36.     build(rc,mid+1,e);
  37.     merge(seg[lc].begin() , seg[lc].end(), seg[rc].begin(), seg[rc].end(),back_inserter(seg[n]));
  38. }
  39.  
  40. int query(int n,int b,int e,int i,int j,int v)
  41. {
  42.     if(b>j || e< i) return 0;
  43.     if(b>=i && e<= j) {
  44.         int k = upper_bound(all(seg[n]), v ) - seg[n].begin();
  45.         return k;
  46.     }
  47.     int mid = (b+e)/2;
  48.     return query(lc,b,mid,i,j,v) + query(rc,mid+1,e,i,j,v);
  49. }
  50.  
  51.  
  52. int main()
  53. {
  54.     fin>>n>>q;
  55.     for(int i = 1; i <= n; i ++ ) {
  56.         fin>>a[i];
  57.         v.pb(a[i]);
  58.     }
  59.     sort(all(v));
  60.     for(int i = 1;i <= n; i ++ ) {
  61.         a[i] = lower_bound(all(v),a[i]) - v.begin() + 1;
  62.     }
  63.     build(1,1,n);
  64.     while(q--)
  65.     {
  66.         int l,r,x;
  67.         fin>>l>>r;
  68.         x=(r - l + 2) / 2;
  69.         int low = 1, high = n , mid, ans ;
  70.         while(low <= high)
  71.         {
  72.             mid = (low + high) >> 1;
  73.             int k = query(1,1,n,l,r,mid);
  74.  
  75.             if(k >= x) {
  76.                 ans = mid;
  77.                 high = mid-1;
  78.             }
  79.             else low = mid+1;
  80.         }
  81.         fout<<v[ans-1]<<'\n';
  82.     }
  83.     return 0;
  84. }
  85.  
RAW Paste Data