제출 #1172861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172861		khangai11	Vudu (COCI15_vudu)	C++20	42 / 140	181 ms	16016 KiB

vudu

#include <iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<deque>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<numeric>
#include<bitset>
#include<iomanip>
#include<cstdlib>
#include<time.h>
#include <functional>
#include <chrono>
#include <thread>
#include <fstream>
#include <random>

using namespace std;

#ifdef _DEBUG
#define prnt(a) cout<<#a<<"="<<a<<endl
#else
#define prnt(a) (void)0
#endif // _DEBUG

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define ull unsigned long long
#define ll int
#define ld long double
#define INF (1LL<<30)
#define INFLL (1LL<<62)
#define MOD 1000000007
#define MOD2 998244353
#define rep(i,st,en) for(ll i=(st);i<(en);++i)
#define vld vector<ld>
#define vll	vector<ll>
#define vvll	vector<vll>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define pii	pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define VS vector<string>
#define MY_PI           3.141592653589793238462643383279502884L
#define all(v) (v).begin(), (v).end()

#define rd(...) __VA_ARGS__; read(__VA_ARGS__)
#define rdv(value,...) value(__VA_ARGS__);cin >> value
template <class T> auto& operator>>(istream& is, vector<T>& xs) {
	for (auto& x : xs) is >> x;
	return is;
}
template <class T> auto& operator<<(ostream& os, vector<T>& xs) {
	int sz = xs.size();
	rep(i, 0, sz) os << xs[i] << " \n"[i + 1 == sz];
	return os;
}
template <class T, class Y> auto& operator<<(ostream& os, pair<T, Y>& xs) {
	os << "{" << xs.first << ", " << xs.second << "}";
	return os;
}
template <class T, class Y> auto& operator>>(istream& is, vector<pair<T, Y>>& xs) {
	for (auto& [x1, x2] : xs) is >> x1 >> x2;
	return is;

}
template <class  ...Args>
auto& read(Args & ...args) { return (cin >> ... >> args); }

#define write(...) writemy(__VA_ARGS__);cout<<"\n"
void writemy() {}
template <typename Head, class  ...Args>
void writemy(const Head& head, const Args & ...args) {
	cout << head << " ";
	writemy(args...);
}


/// <summary>
/// index starts 1
/// </summary>
class BITree {
public:
	vector<ll> v;
	int sz;

	BITree(int n) {
		v.resize(n + 1, 0);
		sz = n;
	}

	void add(int ind, ll val) {
		int i = ind;
		while (i <= sz) {
			v[i] += val;
			i += (i & (-i));
		}
	}

	ll query(int ind) {
		ll r = 0;
		int i = ind;
		if (i > sz) i = sz;
		while (i > 0) {
			r += v[i];
			i -= (i & (-i));
		}
		return r;
	}
};


void solve(ll test) {
	ll rd(n);
	vll a(n + 1);
	rep(i, 1, n + 1) {
		cin >> a[i];
	}
	a[0] = 0;
	ll rd(p);
	rep(i, 1, n + 1) {
		a[i] -= p;
	}
	rep(i, 1, n + 1) {
		a[i] += a[i - 1];
	}
	vpll b(n + 1);
	rep(i, 0, n + 1) {
		b[i] = {a[i],i};
	}
	sort(all(b));
	rep(i, 0, n + 1) {
		a[b[i].second] = i + 1;
	}
	BITree t(n + 2);
	long long ans = 0;
	rep(i, 0, n + 1) {
		ans += t.query(a[i]);
		t.add(a[i], 1);
	}
	cout << ans << "\n";
}

int main() {
	//initFacts(100, MOD2);
	//findPrimes(400000);
	//freopen("four_in_a_burrow_input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int test = 1;
	//cin >> test;
	for (int t = 1; t <= test; t++)
		solve(t);
	return 0;
}

• Subtask 1: 42 / 140