Submission #209881

#	Time	Username	Problem	Language	Result	Execution time	Memory
209881		ZwariowanyMarcin	Vudu (COCI15_vudu)	C++14	140 / 140	442 ms	24016 KiB

vudu

#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 1e6 + 10101;

int n, p, a[N];
vector <LL> v;
LL pref[N];

int f[N];
void add(int x, int c) {
	for (; x < N; x += (x & -x))
		f[x] += c;
}
int qq(int x) {
	int res = 0;
	for (; x; x -= (x & -x))
		res += f[x];
	return res;
}

int pos(LL x) {
	return (int) (lower_bound(all(v), x) - v.begin()) + 1;
}

int main() {
	scanf ("%d", &n);
	rep(i, 1, n) scanf ("%d", a + i);
	scanf ("%d", &p);
	v.pb(0);
	rep(i, 1, n) {
		a[i] -= p;
		pref[i] = pref[i - 1] + a[i];
		v.pb(pref[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	LL ans = 0;
	add(pos(0), 1);
	rep(i, 1, n) {
		ans += qq(pos(pref[i]));
		add(pos(pref[i]), 1);
	}
	printf ("%lld\n", ans);	
		
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140