oj.uz

Submission #87978

# Submission time Handle Problem Language Result Execution time Memory
87978 2018-12-03T10:22:54 Z Good Vudu (COCI15_vudu) C++11
140 / 140
 767 ms 28876 KB 
/*
ID: blackha5
TASK: test
LANG: C++
*/
#include <bits/stdc++.h>

#define ff first
#define ss second
#define Maxn 1000003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
using namespace std;

ll ans;
int n, p;
int a[Maxn];
int T[Maxn * 4];

vector <pair <ll, int> > v;

void upd (int x, int l, int r, int v) {
	if (l == r) {
		T[v] ++;
		return;
	}
	
	if (x <= mid (l, r))
		upd (x, l, mid (l, r), v * 2);
	else
		upd (x, mid (l, r) + 1, r, v * 2 + 1);
	
	T[v] = T[v * 2] + T[v * 2 + 1];
	return;		
}

int get (int x, int y, int l, int r, int v) {
	if (l > y or r < x)
		return 0;
	if (l >= x and r <= y)
		return T[v];
	
	return get (x, y, l, mid (l, r), v * 2) + get (x, y, mid (l, r) + 1, r, v * 2 + 1);		
}

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d", &n);
	
	for (int i = 1; i <= n; i++)
		scanf ("%d", a + i);

	scanf ("%d", &p);
	for (int i = 1; i <= n; i++)
		a[i] -= p;
	
	ll s = 0;	
	for (int i = 1; i <= n; i++) {
		s += a[i];
		v.pb ({s, i});
	}	
	
	v.pb ({0, 0});
	sort (all(v));
	
	int c = 0;
	for (int i = 0; i < v.size(); i++) {
		if (i == 0)
			a[v[i].ss] = ++c;
		else if (v[i].ff != v[i - 1].ff)
			a[v[i].ss] = ++c;
		else
			a[v[i].ss] = c;		
	} 
	
	upd (a[0], 1, c, 1);
	for (int i = 1; i <= n; i++) {
		ans += get (1, a[i], 1, c, 1);
		upd (a[i], 1, c, 1);
	}
	
	printf ("%lld\n", ans);
	return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
vudu.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
vudu.cpp:62:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", a + i);
   ~~~~~~^~~~~~~~~~~~~
vudu.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &p);
  ~~~~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 5 ms 916 KB Output is correct
3 Correct 5 ms 916 KB Output is correct
4 Correct 767 ms 27996 KB Output is correct
5 Correct 416 ms 27996 KB Output is correct
6 Correct 648 ms 27996 KB Output is correct
7 Correct 693 ms 27996 KB Output is correct
8 Correct 587 ms 27996 KB Output is correct
9 Correct 704 ms 28876 KB Output is correct
10 Correct 627 ms 28876 KB Output is correct