Submission #875352

#	Time	Username	Problem	Language	Result	Execution time	Memory
875352		serifefedartar	Vudu (COCI15_vudu)	C++17	140 / 140	402 ms	34128 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 2e6 + 10;

vector<ll> A, cc;
int fen[MAXN];
ll index(ll k) {
	return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}

ll get(int k) {
	ll res = 0;
	while (k > 0) {
		res += fen[k];
		k -= k & -k;
	}
	return res;
}

void add(int k, int val) {
	while (k < MAXN) {
		fen[k] += val;
		k += k & -k;
	}
}

int main() {
	fast
	memset(fen, 0, sizeof(fen));
	int N;
	ll P;
	cin >> N;

	A = vector<ll>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i-1];
	}
	cin >> P;
	for (ll i = 1; i <= N; i++) {
		cc.push_back(P * i - A[i-1]);
		cc.push_back(P * i - A[i] + P - 1);	
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
 
	ll ans = 0;
	for (ll i = 1; i <= N; i++) {
		add(index(P * i - A[i-1]), 1);
		ans += i - get(index(P * i - A[i] + P - 1));
	}

	cout << ans << "\n";
}

• Subtask 1: 140 / 140