Submission #946626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
946626	2024-03-14T20:21:00 Z	Mohamed_Kachef06	Vudu (COCI15_vudu)	C++17	140 / 140	488 ms	58968 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	856 KB	Output is correct
2	Correct	2 ms	860 KB	Output is correct
3	Correct	2 ms	860 KB	Output is correct
4	Correct	488 ms	57940 KB	Output is correct
5	Correct	243 ms	44232 KB	Output is correct
6	Correct	394 ms	51520 KB	Output is correct
7	Correct	393 ms	54736 KB	Output is correct
8	Correct	354 ms	47728 KB	Output is correct
9	Correct	462 ms	58968 KB	Output is correct
10	Correct	395 ms	51088 KB	Output is correct