Submission #1328598


Source Code Expand

Copy

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
int64_t K;
int64_t a[400001];
std::vector<int64_t> v;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);

	in >> N >> K;
	for (int32_t i = 1; i <= N; ++i)
	{
		in >> a[i];
		a[i] -= K;
	}
	for (int32_t i = 1; i <= N; ++i)
	{
		a[i] += a[i - 1];
	}

	int64_t count = 0;
	v.reserve(N);
	v.push_back(0);
	for (int32_t i = 1; i <= N; ++i)
	{
		auto iter = std::upper_bound(v.begin(), v.end(), a[i]);
		count += iter -v.begin();
		v.insert(iter, a[i]);
	}
	/*
	for (int32_t num = 1; num <= N; ++num)
	{
		for (int32_t i = num; i <= N; ++i)
		{
			if ((a[i] - a[i - num]) >= 0) {
				++count;
			}
		}
	}
	*/

	out << count << endl;

	return 0;
}
#endif

Submission Info

Submission Time
Task E - Meaningful Mean
User eiya
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1187 Byte
Status
Exec Time 2103 ms
Memory 4992 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 0 / 600 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 227 ms 4992 KB
b06 2103 ms 2688 KB
b07 2103 ms 2688 KB
b08 2103 ms 3200 KB
b09 2103 ms 2816 KB
b10 2103 ms 2688 KB
b11 1 ms 256 KB
b12 2 ms 256 KB
b13 706 ms 1920 KB
b14 2103 ms 2816 KB
b15 2103 ms 2688 KB
b16 230 ms 4992 KB
b17 1193 ms 4992 KB
b18 2103 ms 2816 KB
b19 2103 ms 2688 KB
b20 2103 ms 2944 KB
b21 2103 ms 3328 KB
b22 2103 ms 2688 KB
b23 2103 ms 3200 KB