oj.uz

Submission #218549

# Submission time Handle Problem Language Result Execution time Memory
218549 2020-04-02T09:23:56 Z socho Vudu (COCI15_vudu) C++14
140 / 140
 838 ms 23928 KB 
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double
 
const int N = 2000005;
long long fw[N];
void update(int x, int v) {
    for (; x<N; x+=x&(-x)) fw[x] += v; 
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
 
int qry(int x) {
	if (x <= 0) return 0;
	int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
 
int qry(int a, int b) {
	return qry(b+1);
}
 
void upd(int x, int v) {
	x++;
	for (; x<N; x+=x&(-x)) fw[x] += v; 
}
 
signed main() {
	
	int n;
	cin >> n;
	long long arr[n];
	for (int i=0; i<n; i++) cin >> arr[i];
	int p;
	cin >> p;
	
	for (int i=0; i<n; i++) arr[i] -= p;
	
	long long pf[n];
	pf[0] = arr[0];
	for (int i=1; i<n; i++) pf[i] = pf[i-1] + arr[i];
	
	sort(pf, pf+n);
	
	long long sm = 0;
	long long ans = 0;
	
	for (int i=0; i<n; i++) {
		if (pf[i] >= 0) ans++;
	}
	
	for (int i=0; i<n; i++) {
		sm += arr[i];
		int low = lower_bound(pf, pf+n, sm) - pf;
		ans += qry(0, low);
		// cout << i << '>' << ans << endl; 
		upd(low, 1);
	}
	
	cout << ans << endl;
	
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 838 ms 23380 KB Output is correct
5 Correct 441 ms 13304 KB Output is correct
6 Correct 696 ms 20724 KB Output is correct
7 Correct 741 ms 21480 KB Output is correct
8 Correct 640 ms 18680 KB Output is correct
9 Correct 816 ms 23928 KB Output is correct
10 Correct 711 ms 20856 KB Output is correct