Submission #88414

#	Time	Username	Problem	Language	Result	Execution time	Memory
88414		Koschei	Vudu (COCI15_vudu)	C++17	126 / 140	372 ms	66560 KiB

vudu

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int n;
long long c;
long long p, r, a[1000000];
vector< pair<long long, int> > prefiks_sume;
int tree[1000005] = {0};

void add(int x)
{
	while (x < 1000005)
	{
		tree[x]++;
		x += x & (-x);
	}
}

long long gets(int x)
{
	long long s = 0;
	while (x)
	{
		s += tree[x];
		x -= x & (-x);
	}
	return s;	
}
 
int main()
{
	prefiks_sume.push_back(make_pair(0, 1));
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
	}
	scanf("%lld", &p);
	for (int i = 0; i < n; i++)
	{
		r += a[i] - p;
		prefiks_sume.push_back(make_pair(r, i+2));	
	}
	sort(prefiks_sume.begin(), prefiks_sume.end());
	for (int i = 0; i <= n; i++)
	{
		c += gets(prefiks_sume[i].second-1);
		add(prefiks_sume[i].second);
	}
	printf("%lld", c);
	return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
vudu.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &p);
  ~~~~~^~~~~~~~~~~~

• Subtask 1: 126 / 140