제출 #1160359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160359		Doncho_Bonboncho	Vudu (COCI15_vudu)	C++17	140 / 140	186 ms	39476 KiB

vudu

#include <algorithm>
#include <bits/stdc++.h>
#include <utility>
#include <vector>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 +7;
const int MAX_N = 1e6 + 42;

ll fen[MAX_N];
void fenUpdate( int x, int val = 1 ){
	cerr << "update" << out( x ) << endl;
	while( x < MAX_N ){
		fen[x] += val;
		x += x & (-x );
	}
}

int fenQuery( int x ){
	ll nas = 0;
	while( x ){
		nas += fen[x];
		x -= x & (-x);
	}

	return nas;
}

int main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n;
	std::cin >> n;
	std::vector< int > a( n+1 );
	for( int j=1 ; j <= n ; j++ ) std::cin >> a[j];

	int P;
	std::cin >> P;
	for( int j=1 ; j <= n ; j++ ) a[j] -= P;

	std::vector< ll > pref( n+1, 0 );
	std::vector< std::pair< ll, ll > > v;
	for( int j=1 ; j <= n ; j++ ){
		pref[j] = pref[j-1] + a[j];
		v.push_back({ pref[j], j });
	}
	v.push_back({ 0, 0 });

	for( int i=0 ; i <= n ; i++ ) cerr << out( i ) << out( pref[i] ) << endl;

	std::sort( v.begin(), v.end() );
	std::vector< int > b( n+1 );
	for( int i=0 ; i <= n ; i++ ){
		b[ v[i].second ] = i+1;
	}
	
	for( int i=0 ; i <= n ; i++ ){
		cerr << out( i ) << out( b[i] ) << endl;
	}

	ll nas = 0;
	for( int i=0 ; i <= n ; i++ ){
		nas += fenQuery( b[i] );
		fenUpdate( b[i] );
	}

	std::cout << nas << endl;

	/*
	ll nas = 0;
	for( int i=0 ; i < n ; i++ ){
		for( int j=i ; j < n ; j++ ){
			ll currS = 0;
			for( int k=i ; k <= j ; k++ ){
				currS += a[k];
			}

			cerr << out( i ) << out( j ) << out( currS ) << endl;
			nas += ( currS >= 0 );
		}
	}

	std::cout << nas << endl;
	*/



	return 0;
}

• Subtask 1: 140 / 140