oj.uz

Submission #875349

# Submission time Handle Problem Language Result Execution time Memory
875349 2023-11-19T07:55:57 Z serifefedartar Vudu (COCI15_vudu) C++17
42 / 140
 229 ms 65536 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 = 1e6 + 10;

vector<ll> A, cc;
int fen[MAXN];
int 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, 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
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4572 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Runtime error 211 ms 64072 KB Execution killed with signal 11
5 Runtime error 120 ms 37816 KB Execution killed with signal 11
6 Runtime error 229 ms 60364 KB Execution killed with signal 11
7 Runtime error 186 ms 61556 KB Execution killed with signal 11
8 Runtime error 192 ms 51380 KB Execution killed with signal 11
9 Runtime error 209 ms 65536 KB Execution killed with signal 11
10 Runtime error 179 ms 62192 KB Execution killed with signal 11