Submission #946626

#	Time	Username	Problem	Language	Result	Execution time	Memory
946626		Mohamed_Kachef06	Vudu (COCI15_vudu)	C++17	140 / 140	488 ms	58968 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int a[(int)1e6+1]; 
vector<int> coco; 
int n , p;

int id(int x){
   return upper_bound(coco.begin() , coco.end() , x) - coco.begin() ; 
}


struct SegmentTree{
    vector<int> seg;
    int m ; 
    void init(int n){
      m = 1<<(__lg(n-1)+1); 
      seg.resize(2*m);
    }
    void update(int id , int val , int s , int e , int p){
      if (s == e) {seg[p] += val; return;}
      else if (id <= (s+e)/2) update(id , val , s , (s+e)/2 , 2*p);
      else update(id , val , (s+e)/2 + 1 , e  , 2*p+1) ;
      seg[p] = seg[2*p] + seg[2*p+1];
    }
    int get(int l , int r , int s, int e , int p){
      if (l > e || r < s) return 0;
      else if (l <= s && r >= e) return seg[p];
      return get(l , r  , s , (s+e)/2 , 2*p) + get(l , r , (s+e)/2 + 1 , e , 2*p+1); 
    }
    void update(int id , int val){
      update(id , val , 1 , m ,1);
    }
    int get(int l , int r) {return get(l , r , 1 , m , 1); }
};

   SegmentTree st; 



void doWork(){
   cin >> n ;
   for (int i = 1 ; i <= n ; i++) cin >> a[i];
   cin >> p;
   for (int i = 1 ; i <= n ; i++){
      a[i] += a[i-1]; 
   }
   for (int i = 0 ; i <= n ; i++) coco.push_back(a[i] - p*i); 
   st.init(2*n);
   sort(coco.begin() , coco.end()); 
   int ans = 0;
   st.update(id(0) , 1); 
   for (int r = 1 ; r <= n ; r++){
      ans += st.get(1 , id(a[r] - p*r)); 
      st.update(id(a[r] - p*r) , 1); 
   }
   cout << ans; 
}

signed main(){
   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
   doWork(); 
}

• Subtask 1: 140 / 140