Submission #821751

#	Time	Username	Problem	Language	Result	Execution time	Memory
821751		dungz	Vudu (COCI15_vudu)	C++17	42 / 140	1075 ms	65536 KiB

vudu

#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
int tree[4000005];
int a[1000005];
vector<int> vc;
map<int,int> danh;
int d=0;
int ans=0;
void update(int node,int l,int r,int u)
{
	if(l>u or r<u) return;
	if(l==r)
	{
		tree[node]+=1;
		return; 
	}
	int m=(l+r)/2;
	update(node*2,l,m,u);
	update(node*2+1,m+1,r,u);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int get(int node,int l,int r,int u,int v)
{
	if(l>v or r<u) return 0;
	if(l>=u and r<=v) return tree[node];
	int m=(l+r)/2;
	return get(node*2,l,m,u,v)+get(node*2+1,m+1,r,u,v);
}
int main(){

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,p;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}	
	cin>>p;
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i]+a[i-1]-p;
		vc.push_back(a[i]);
	}
	vc.push_back(0);
	sort(vc.begin(),vc.end());
	for(auto i:vc)
	{
		if(!danh[i])
		{
			danh[i]=++d;
		}
	}
	update(1,1,d,danh[0]);
	for(int i=1;i<=n;i++)
	{
		int temp=--upper_bound(vc.begin(),vc.end(),a[i])-vc.begin();
		if(temp<0) continue;
		temp=danh[vc[temp]];
		ans+=get(1,1,d,1,temp);
		update(1,1,d,danh[a[i]]);
	}
	cout<<ans;
}
/*
-1 0 0
*/

• Subtask 1: 42 / 140