oj.uz

답안 #946626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946626 2024-03-14T20:21:00 Z Mohamed_Kachef06 Vudu (COCI15_vudu) C++17
140 / 140
 488 ms 58968 KB 
#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

# 결과 실행 시간 메모리 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