Submission #621177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
621177	2022-08-03T13:34:29 Z	sword060	Vudu (COCI15_vudu)	C++17	140 / 140	606 ms	57672 KB

vudu

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
long long seg[4*N],xd,ans,a[N],x,k,mp[N];
pair<long long,int>comp[N];
long long query(int i,int l,int r,int s,int e){
	if(l>e||r<s)return 0;
	if(l>=s&&r<=e){
	  return seg[i];
	}
	int mid=(l+r)/2;
	return (query((i<<1),l,mid,s,e)+query((i<<1|1),mid+1,r,s,e));
}
void update(int i,int l,int r,int s){
	if(l>s||r<s)return;
	if(l==s&&r==s){
		seg[i]++;
		return;
	}
	int mid = (l+r)/2;
	update((i<<1),l,mid,s);
	update((i<<1|1),mid+1,r,s);
	seg[i]=(seg[i<<1]+seg[i<<1|1]);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>x;
	for(int i=1;i<=x;i++)cin>>a[i];
	cin>>k;
	for(int i=1;i<=x;i++){
	  a[i]-=k;
	  xd+=a[i];
	  comp[i].first=xd;
	  comp[i].second=i;
	}
	sort(comp,comp+x+1);
	int z=0;
	for(int i=0;i<=x;i++){
	  if(!i||comp[i-1].first!=comp[i].first)z++;
	  mp[comp[i].second]=z;
	}
	xd=0;
	update(1,0,N,mp[0]);
	for(int i=1;i<=x;i++){
	  ans+=query(1,0,N,0,mp[i]);
	  update(1,0,N,mp[i]);
	}
	cout<<ans;
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	768 KB	Output is correct
2	Correct	3 ms	724 KB	Output is correct
3	Correct	4 ms	724 KB	Output is correct
4	Correct	605 ms	55732 KB	Output is correct
5	Correct	319 ms	31688 KB	Output is correct
6	Correct	500 ms	49408 KB	Output is correct
7	Correct	516 ms	51452 KB	Output is correct
8	Correct	454 ms	44668 KB	Output is correct
9	Correct	606 ms	57672 KB	Output is correct
10	Correct	477 ms	50140 KB	Output is correct