제출 #1231050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231050		djsksbrbf	Vudu (COCI15_vudu)	C++20	140 / 140	254 ms	24020 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;
#define int ll

int seg[MAX];
int n, m, p;

int query(int x){
	int cnt = 0;
	while(x >= 1){
		cnt += seg[x];
		x -= (x & -x);
	}
	
	return cnt;
}

void upd(int x){
	while(x <= m){
		seg[x]++;
		x +=(x & -x);
	}
}

vector <int> v;
int sear(int x){
	int t = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
	return t;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	int a[n + 1];
	for(int i = 1 ;i <= n ; i++)cin >> a[i];
	cin >> p;
	
	ll pref = 0, ans = 0;
	for(int i = 1 ; i <= n ; i++){
		pref += a[i];
		a[i] = pref - p*i;
		v.pb(a[i]);
	}
	v.pb(0);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	m = (int)v.size();
	
	upd(sear(0));
	for(int i = 1 ; i <= n ; i++){
		ans += query(sear(a[i]));
		upd(sear(a[i]));
	}
	cout << ans << endl;
	
	return 0;
}

• Subtask 1: 140 / 140