oj.uz

Submission #88414

# Submission time Handle Problem Language Result Execution time Memory
88414 2018-12-05T18:07:51 Z Koschei Vudu (COCI15_vudu) C++17
126 / 140
 372 ms 66560 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 760 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 4 ms 848 KB Output is correct
4 Correct 348 ms 36472 KB Output is correct
5 Correct 202 ms 36472 KB Output is correct
6 Correct 314 ms 47048 KB Output is correct
7 Correct 321 ms 48908 KB Output is correct
8 Correct 284 ms 50492 KB Output is correct
9 Correct 372 ms 65188 KB Output is correct
10 Runtime error 330 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.