Advertisement
Josif_tepe

Untitled

Feb 27th, 2023
527
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1.     #include <iostream>
  2.     #include <vector>
  3.     #include <set>
  4.     #include <map>
  5.     #include <cstring>
  6.     #include <algorithm>
  7.     #include <stack>
  8.     #include <queue>
  9.  
  10.     using namespace std;
  11.     vector<int>v;
  12.     const int maxn=2e5;
  13.  
  14.     int segment[maxn*3];
  15.     void build_tree(int L, int R, int pos){
  16.     if(L==R){
  17.         segment[pos]=v[L];
  18.     }
  19.     else{
  20.         int middle=(L+R)/2;
  21.         build_tree(L, middle, pos*2);
  22.         build_tree(middle+1, R, pos*2+1);
  23.         segment[pos]=min(segment[2*pos], segment[2*pos+1]);
  24.  
  25.     }
  26.     }
  27.     ///l r i l r j l r
  28.     int query(int L, int R, int pos, int i, int j){
  29.     if(i<=L and j>=R){
  30.         return segment[pos];
  31.     }
  32.     if(R<i or j<L){
  33.         return 2e9;
  34.     }
  35.     int middle=(R+L)/2;
  36.     return min(query(L, middle, pos*2, i, j), query(middle+1, R, pos*2+1, i, j));
  37.     }
  38.  
  39.  
  40.     int main() {
  41.     int n, k, l;
  42.  
  43.  
  44.  
  45.     cin>>n>>l>>k;
  46.     for(int i=0; i<n; i++){
  47.     int a; cin>>a;
  48.     v.push_back(a);
  49.     }
  50.     build_tree(0, n-1, 1);
  51.     int counter=0;
  52.     for(int i=0; i<v.size(); i++){
  53.         if(v[i]<l){
  54.             continue;
  55.         }
  56.         if(i + k >= v.size()) {
  57.             continue;
  58.         }
  59.         if(query(0, n-1, 1, i+1, i+k)>=l){
  60.         counter++;
  61.         }
  62.  
  63.     }
  64.     cout<<counter;
  65.     return 0;
  66.     }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement