Submission #105108

#	Time	Username	Problem	Language	Result	Execution time	Memory
105108		groeneprof	Vudu (COCI15_vudu)	C++14	42 / 140	383 ms	66560 KiB

vudu

#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 1;
const int inf = 1e16;

struct node{
	node* child1;
	node* child2;
	int val = 0;
	node(){
		child1 = 0;
		child2 = 0;
		val = 0;
	}
	void check(){
		if(child1==0){
			child1 = new node;
			child2 = new node;
		}
	}
	int update(int i, int nval, int L = 0, int R = 2*inf){
		//P("Update "<<i<<" "<<nval<<" "<<L<<" "<<R);
		if(i<L||i>R){
			return val;
		}
		if(L == R){
			return val = val+nval;
		}
		check();
		return val = child1->update(i, nval, L, (L+R)/2ll)+child2->update(i, nval, (L+R)/2ll+1ll, R);
	}
	int query(int i, int j, int L = 0, int R = 2*inf){
		//P("query "<<i<<" "<<j<<" "<<L<<" "<<R);
		if(j<L||i>R){
			return 0;
		}
		if(i<=L&&R<=j){
			return val;
		}
		check();
		return child1->query(i, j, L, (L+R)/2ll)+child2->query(i, j, (L+R)/2ll+1ll, R);
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//cout<<(-1)/2<<endl;
	int N;
	cin>>N;
	vector<int> a(N);
	F(i, N){
		cin>>a[i];
	}
	int P;
	cin>>P;
	int sum = 0, tot= 0;
	node st;
	st.update(inf,1);
	F(i, N){
		a[i]-=P;
		sum+=a[i];
		tot+=st.query(0, sum+inf);
		//(st.query(0, sum+inf));
		st.update(sum+inf, 1);
	}
	cout<<tot;
	return 0;
}

• Subtask 1: 42 / 140