Submission #1326775

---

Source Code Expand

// {{{ Boilerplate Code <--------------------------------------------------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define ALL(A)     (A).begin(), (A).end()

using namespace std;

// }}}

int main(){
	long long N,K;
	vector<long long> a;
	cin>>N>>K;

	long long currentsum=0;

	a.push_back(0);
	FOR(i,0,N){
		long long tmp;
		cin>>tmp;
		tmp-=K;
		currentsum+=tmp;
		a.push_back(currentsum);
	}

	vector<long long> sorted;
	vector<long long> tmp;

	long long freq=sqrt(N)*2;

	long long ret=0;

	FOR(i,0,N+1){
		long long t=0;

		FOR(j,0,tmp.size()){
			if(tmp[j]<=a[i]){
				t++;
			}
		}
		tmp.push_back(a[i]);

		long long upper=sorted.size();
		long long lower=0;

		while(lower<upper){
			long long mid=(lower+upper)/2;

			if(sorted[mid]<=a[i]){
				lower=mid+1;
			}else{
				upper=mid;
			}
		}


		ret+=t+lower;

		if(i%freq==0){
			FOR(j,0,tmp.size()){
				sorted.push_back(tmp[j]);
			}
			tmp.clear();
			sort(ALL(sorted));
		}
	}

	cout<<ret<<endl;
}

Submission Info

Judge Result