fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<map>
  3. #include<string>
  4. #define ll          long long
  5. #define pb          push_back
  6. #define mp          make_pair
  7. #define pii         pair<int,int>
  8. #define vi          vector<int>
  9. #define all(a)      (a).begin(),(a).end()
  10. #define F           first
  11. #define S           second
  12. #define sz(x)       (int)x.size()
  13. #define hell        1000000007
  14. #define endl        '\n'
  15. #define rep(i,a,b)  for(int i=a;i<b;i++)
  16. #define rep1(i,a,b) for(ll i=a;i<= b;i++)
  17. #define PI          3.14159
  18. #define MAX         1000001
  19. //sconst ll maxn = (ll)1e18;
  20. using namespace std;
  21. ll ar[100001];
  22. ll tree[400001];
  23.  
  24. class SegmentTree
  25. {
  26.   ll n;
  27.  
  28.   void set(ll node, ll val)
  29.   {
  30.     tree[node] = val;
  31.   }
  32.  
  33.   void calc(ll node, ll &d, ll &lChild, ll &rChild)
  34.   {
  35.     d = max(lChild,rChild);
  36.     return;
  37.   }
  38.  
  39.   void build(ll s, ll e, ll node)
  40.   {
  41.     if(s==e) //leaf
  42.       set(node,ar[s]);
  43.     else
  44.     {
  45.       int m = s + (e-s)/2;
  46.       build(s,m,2*node);
  47.       build(m+1,e,2*node+1);
  48.       calc(node,tree[node],tree[2*node],tree[2*node+1]);
  49.     }
  50.   }
  51.  
  52.   ll query(ll l, ll r, ll s, ll e, ll node)
  53.   {
  54.     ll d = 0;
  55.     if(s>r || e<l)
  56.       return d;
  57.     else if(s>=e && e<=r)
  58.       return tree[node];
  59.  
  60.     int m = s+(e-s)/2;
  61.     if(l>m)
  62.       return query(l,r,m+1,e,2*node+1);
  63.     else if(r<=m)
  64.       return query(l,r,s,m,2*node);
  65.     else
  66.     {
  67.       ll lQuery = query(l,r,s,m,2*node);
  68.       ll rQuery = query(l,r,m+1,e,2*node+1);
  69.       calc(node,d,lQuery,rQuery);
  70.       return d;
  71.     }
  72.   }
  73.  
  74. public:
  75.   SegmentTree(int n)
  76.   {
  77.     this->n = n;
  78.     build(1,n,1);
  79.   }
  80.  
  81.   int query(int l, int r)
  82.   {
  83.     return query(l,r,1,n,1);
  84.   }
  85.  
  86. };
  87. int main()
  88. {
  89.   ios_base::sync_with_stdio(false);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92.     ll n;
  93.     cin >> n;
  94.     for(ll i = 1; i <= n ;i++)
  95.     {
  96.       cin >> ar[i];
  97.     }
  98.     SegmentTree s1(n);
  99.     ll k;
  100.     cin >> k;
  101.     for(ll i = 1; i <= n - k + 1; i++)
  102.     {
  103.       cout << s1.query(i,i + k - 1) << " ";
  104.     }
  105.     return 0;
  106. }
Time limit exceeded #stdin #stdout 5s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MO5Wiq
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!