oj.uz

답안 #875347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875347 2023-11-19T07:52:42 Z serifefedartar Vudu (COCI15_vudu) C++17
42 / 140
 392 ms 65540 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);	
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Runtime error 392 ms 65536 KB Execution killed with signal 9
5 Runtime error 151 ms 50092 KB Execution killed with signal 11
6 Runtime error 282 ms 65536 KB Execution killed with signal 11
7 Runtime error 337 ms 65540 KB Execution killed with signal 9
8 Runtime error 238 ms 65536 KB Execution killed with signal 11
9 Runtime error 368 ms 65536 KB Execution killed with signal 9
10 Runtime error 352 ms 65536 KB Execution killed with signal 9