Submission #1230213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230213		altern23	Vudu (COCI15_vudu)	C++20	140 / 140	232 ms	23896 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll a[MAXN + 5];

struct BIT{
	ll N;
	vector<ll> bit;
	BIT(ll _n){
		N = _n;
		bit.resize(N + 5);
	}
	
	void upd(ll idx, ll val){
		for(; idx <= N; idx += idx & -idx) bit[idx] += val;
	}
	ll get(ll idx){
		ll ans = 0;
		for(; idx >= 1; idx -= idx & -idx) ans += bit[idx];
		return ans;
	}
	ll query(ll l, ll r) { return get(r) - get(l - 1); }
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		vector<ll> v;
		v.push_back(0);
		ll now = 0;
		for(ll i = 1; i <= N; i++){
			cin >> a[i];
		}
		
		ll K; cin >> K;
		for(ll i = 1; i <= N; i++){
			now += a[i];
			v.push_back(now - i * K);
		}
		
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		
		ll M = v.size();
		BIT bit(M);
		bit.upd(lower_bound(v.begin(), v.end(), 0) - v.begin() + 1, 1LL);
		
		now = 0;
		ll ans = 0;
		for(ll i = 1; i <= N; i++){
			now += a[i];
			ll pos = lower_bound(v.begin(), v.end(), now - i * K) - v.begin() + 1;
			ans += bit.query(1, pos);
			bit.upd(pos, 1);
		}
		
		cout << ans << "\n";
	}
}

/*

*/

• Subtask 1: 140 / 140