oj.uz

Submission #209879

# Submission time Handle Problem Language Result Execution time Memory
209879 2020-03-15T20:21:49 Z ZwariowanyMarcin Vudu (COCI15_vudu) C++14
42 / 140
 425 ms 29780 KB 
#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(int 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

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
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Incorrect 393 ms 28752 KB Output isn't correct
5 Incorrect 258 ms 20188 KB Output isn't correct
6 Incorrect 361 ms 25548 KB Output isn't correct
7 Incorrect 351 ms 26576 KB Output isn't correct
8 Incorrect 289 ms 23260 KB Output isn't correct
9 Incorrect 425 ms 29780 KB Output isn't correct
10 Incorrect 378 ms 25936 KB Output isn't correct