oj.uz

Submission #209881

# Submission time Handle Problem Language Result Execution time Memory
209881 2020-03-15T20:22:55 Z ZwariowanyMarcin Vudu (COCI15_vudu) C++14
140 / 140
 442 ms 24016 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(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

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.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 504 KB Output is correct
4 Correct 442 ms 23248 KB Output is correct
5 Correct 240 ms 15068 KB Output is correct
6 Correct 405 ms 20688 KB Output is correct
7 Correct 386 ms 21456 KB Output is correct
8 Correct 331 ms 18768 KB Output is correct
9 Correct 439 ms 24016 KB Output is correct
10 Correct 375 ms 20948 KB Output is correct