# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
87976 | Good | Vudu (COCI15_vudu) | C++11 | 717 ms | 63272 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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});
}
sort (all(v));
v.pb ({0, 0});
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |