oj.uz

Submission #98435

# Submission time Handle Problem Language Result Execution time Memory
98435 2019-02-23T16:48:08 Z luciocf Vudu (COCI15_vudu) C++14
112 / 140
 995 ms 66560 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,avx,mmx,popcnt,tune=native")

using namespace std;

const int maxn = 1e6+10;

typedef long long ll;

struct node
{
	node *l, *r;
	ll v;
	int w, sz;

	node(ll vv)
	{
		l = r = NULL;
		v = vv, sz = 1, w = rand();
	}
};

typedef node*& node_t;

int sz(node *t)
{
	return (t ? t->sz : 0);
}

void op(node *t)
{
	if (t) t->sz = sz(t->l)+sz(t->r)+1;
}

void split(node *t, node_t l, node_t r, ll x)
{
	if (!t) return void(l=r=NULL);

	if (t->v > x) split(t->l, l, t->l, x), r = t;
	else split(t->r, t->r, r, x), l = t;

	op(t);
}

void insert(node_t t, node *it)
{
	if (!t) t = it;
	else if (it->w > t->w) split(t, it->l, it->r, it->v), t = it;
	else insert((it->v > t->v ? t->r : t->l), it);

	op(t);
}

int query(node *t, ll x)
{
	if (!t) return 0;
	else if (t->v > x) return sz(t->r)+1+query(t->l, x);
	return query(t->r, x);
}

int num[maxn];

ll soma[maxn];

#define gc getchar_unlocked
inline int scan(){
	int n=0, x=gc();
	for(;x<'0'||x>'9';x=gc()){}
	for(;!(x<'0'||x>'9');x=gc()) n = 10*n + x-'0';
	return n;
}

int main(void)
{
	ios::sync_with_stdio(false), cout.tie(0);
	int n, p;
	n = scan();

	for (int i = 1; i <= n; i++)
		num[i] = scan();

	p = scan();

	soma[0] = -p;
	for (int i = 1; i <= n; i++)
		soma[i] = soma[i-1]+(ll)num[i]-(ll)p;

	ll ans = 0LL;
	node *t = NULL;
	
	node *it = new node(soma[0]);
	insert(t, it);

	for (int i = 1; i <= n; i++)
	{
		ans += (ll)i-(ll)query(t, soma[i]);

		it = new node(soma[i]);
		insert(t, it);
	}

	cout << ans << '\n';
}

Subtask #1
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 5 ms 660 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Runtime error 995 ms 66524 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Correct 456 ms 37924 KB Output is correct
6 Correct 665 ms 58868 KB Output is correct
7 Correct 625 ms 61432 KB Output is correct
8 Correct 678 ms 53156 KB Output is correct
9 Runtime error 795 ms 66560 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Correct 671 ms 59772 KB Output is correct