Submission #924097

#	Time	Username	Problem	Language	Result	Execution time	Memory
924097		TIN	Vudu (COCI15_vudu)	C++17	0 / 140	42 ms	65536 KiB

vudu

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

#define sz(v) (int) (v).size()
#define all(v) (v).begin(), (v).end()

typedef long long ll;

const int N = 1e6 + 5;

int n;
ll a[N];
ll P;
ll sum;
vector<ll> p;
ll ans = 0;
vector<ll> ST[4 * N];

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

vector<ll> Merge(vector<ll> a, vector<ll> b) {
	int n = a.size(), m = b.size();
	vector<ll> c;
	int i = 0, j = 0;
	while (i < n && j < m) {
		if (a[i] <= b[j]) c.push_back(a[i++]);
		else c.push_back(b[j++]);
	}
	while (i < n) c.push_back(a[i++]);
	while (j < m) c.push_back(b[j++]);
	return c;
}

void build(int id, int l, int r) {
	if (l == r) {
		ST[id].push_back(p[l]);
		return;
	}
	int m = (l + r) / 2;
	build(id * 2, l, m);
	build(id * 2 + 1, m + 1, r);
	ST[id] = Merge(ST[id * 2], ST[id * 2 + 1]);
}

ll query(int id, int l, int r, int u, int v, ll k) {
	if (v < l || r < u) return 0LL;
	if (u <= l && r <= v) {
		int pos = lower_bound(all(ST[id]), k + 1) - ST[id].begin();
		return pos;
	}
	int m = (l + r) / 2;
	return query(id * 2, l, m, u, v, k) + query(id * 2 + 1, m + 1, r, u, v, k);
}

void Solve() {
	//Your Code
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> P;
	sum = 0;
	p.push_back(sum);
	for (int i = 1; i <= n; i++) {
		sum += a[i] - P;
		p.push_back(sum);
	}
	build(1, 0, n);
	for (int i = 1; i <= n; i++) ans += query(1, 0, n, 0, i - 1, p[i]);
	cout << ans << '\n';
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message (stderr)

vudu.cpp: In function 'void Task()':
vudu.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen(FNAME".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
vudu.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(FNAME".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 140