제출 #947548

#제출 시각아이디문제언어결과실행 시간메모리
947548goduadzesabaVudu (COCI15_vudu)C++17
42 / 140
545 ms65536 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,a[N],p,x,f[N],anss;
map <int,int> mp; set <int> s;
void upd(int ind,int val){
	for (int i=ind; i<N; i+=i&(-i))
		f[i]+=val;
}
int get(int ind){
	int ans=0;
	for (int i=ind; i>0; i-=i&(-i))
		ans+=f[i];
	return ans;
}
signed main(){
	cin>>n;
	for (int i=1; i<=n; i++)
		cin>>a[i];
	cin>>p; s.insert(0);
	for (int i=1; i<=n; i++){
		a[i]-=p; a[i]+=a[i-1];
		s.insert(a[i]);
	}
	for (int it:s){
		x++; mp[it]=x;
	}
	upd(mp[0],1);
	for (int i=1; i<=n; i++){
		a[i]=mp[a[i]];
		anss+=get(a[i]);
		upd(a[i],1);
	}
	cout<<anss;
}
#Verdict Execution timeMemoryGrader output
Fetching results...