oj.uz

Submission #875352

# Submission time Handle Problem Language Result Execution time Memory
875352 2023-11-19T08:13:42 Z serifefedartar Vudu (COCI15_vudu) C++17
140 / 140
 402 ms 34128 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 402 ms 34128 KB Output is correct
5 Correct 203 ms 29824 KB Output is correct
6 Correct 336 ms 32960 KB Output is correct
7 Correct 351 ms 32964 KB Output is correct
8 Correct 290 ms 32864 KB Output is correct
9 Correct 377 ms 32860 KB Output is correct
10 Correct 325 ms 31428 KB Output is correct