oj.uz

Submission #718800

# Submission time Handle Problem Language Result Execution time Memory
718800 2023-04-04T21:36:09 Z Doncho_Bonboncho Vudu (COCI15_vudu) C++14
140 / 140
 255 ms 45248 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 240 ms 43776 KB Output is correct
5 Correct 145 ms 26352 KB Output is correct
6 Correct 202 ms 38812 KB Output is correct
7 Correct 255 ms 40352 KB Output is correct
8 Correct 187 ms 35060 KB Output is correct
9 Correct 251 ms 45248 KB Output is correct
10 Correct 197 ms 39340 KB Output is correct