제출 #718800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718800		Doncho_Bonboncho	Vudu (COCI15_vudu)	C++14	140 / 140	255 ms	45248 KiB

vudu

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;

ll pref[MAX_N];

std::vector<std::pair<ll, int>> v;
int ind[MAX_N];

ll fen[MAX_N];
ll query( int x ){
	//std::cerr<<" query  "<<x<<"\n";
	ll nas = 0;
	while( x ){
		nas += fen[x];
		x -= x&-x;
	}
	return nas;
}

void update( int x ){
	//std::cerr<<" update  "<<x<<"\n";
	while( x <= MAX_N ){
		fen[x] ++;
		x += x&-x;
	}
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	for( int i=1 ; i<=n ; i++ ) std::cin>>pref[i];

	int k;
	std::cin>>k;
	for( int i=1 ; i<=n ; i++ ){
		pref[i] += pref[i-1] - k;
		v.push_back({pref[i], i});
	}

	v.push_back({0, 0});

	std::sort( v.begin(), v.end() );

	for( int i=0 ; i<=n ; i++ ) ind[v[i].second] = i +1;
	ll nas = 0;
	for( int i=0 ; i<=n ; i++ ){
		nas += query( ind[i] );
		update(ind[i]);
	}

	std::cout<<nas<<"\n";

	return 0;
}

• Subtask 1: 140 / 140