Submission #620444

#	Time	Username	Problem	Language	Result	Execution time	Memory
620444		sword060	Vudu (COCI15_vudu)	C++17	56 / 140	785 ms	65536 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
long long seg[4*N];
vector<long long>comp;
map<long long,int>mp;
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);
	int x,k;cin>>x;
	long long a[x],ans=0,xd=0;
	for(int i=0;i<x;i++)cin>>a[i];
	cin>>k;
	for(int i=0;i<x;i++)a[i]-=k;
	comp.push_back(0);
	for(int i=0;i<x;i++){
	  xd+=a[i];
	  comp.push_back(xd);
	}
	sort(comp.begin(),comp.end());
	int z=0;
	for(int i=0;i<comp.size();i++)if(mp.find(comp[i])==mp.end())mp[comp[i]]=z++;
	xd=0;
	update(1,0,N,mp[0]);
	for(int i=0;i<x;i++){
	  xd+=a[i];
	  ans+=query(1,0,N,0,mp[xd]);
	  update(1,0,N,mp[xd]);
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(int i=0;i<comp.size();i++)if(mp.find(comp[i])==mp.end())mp[comp[i]]=z++;
      |              ~^~~~~~~~~~~~

• Subtask 1: 56 / 140