Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1.  
  2.  
  3. #include <iostream>
  4. #include <map>
  5. #include <vector>
  6. #include "algorithm"
  7. #include <queue>
  8. using namespace std;
  9. void build(int v, int l ,int  r, vector <int> & derev,const vector <int> & mas )
  10. {
  11.     if (r-l==1){
  12.         derev[v] = mas[l];
  13.         return;
  14.     }
  15.     int mid = (l+r)>>1;
  16.     build(v*2+1,l , mid, derev, mas);
  17.     build(v*2+2, mid, r, derev, mas);
  18.     derev[v]=  min (derev[v*2+1], derev[v*2+2]);
  19. }
  20. int Quest (int v ,int vl, int vr , int l ,int r,const vector <int> & derev )
  21. {
  22.     if (vl>=l && vr <=r)
  23.         return derev[v] ;
  24.     int mid = (vl+vr)>>1;
  25.     int mx = 2e31;
  26.     if (l<mid)
  27.         mx = Quest(v*2+1, vl, mid, l,r, derev);
  28.     if (r> mid)
  29.         mx = min (Quest(v*2+2,mid, vr, l, r, derev),mx);
  30.     return mx;
  31. }
  32.  
  33.  
  34. int main(int argc, const char * argv[]) {
  35.     // insert code here...
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);
  38.     int n, k;
  39.     cin >>n>>k;
  40.     vector <int> g(n);
  41.     vector <int >derev (4*n);
  42.     for (int i = 0 ;i<n;++i)
  43.         cin >>g[i];
  44.     build(0, 0,n , derev, g);
  45.     for (int i = 0 ;i+k-1<n;++i)
  46.         cout << Quest(0, 0, n, i,i+k, derev)<<endl;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement