Submission #947548

#	Time	Username	Problem	Language	Result	Execution time	Memory
947548		goduadzesaba	Vudu (COCI15_vudu)	C++17	42 / 140	545 ms	65536 KiB

vudu

#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;
}

• Subtask 1: 42 / 140