Submission #218548

#	Time	Username	Problem	Language	Result	Execution time	Memory
218548		socho	Vudu (COCI15_vudu)	C++14	14 / 140	842 ms	33432 KiB

vudu

#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, qry(low, low)-qry(low-1, low-1)+1);
	}
	
	cout << ans;
	
}

• Subtask 1: 14 / 140