oj.uz

답안 #26674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26674 2017-07-04T15:51:14 Z szawinis Vudu (COCI15_vudu) C++14
140 / 140
 289 ms 38512 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e6)+1;

int n, p, f[MAX];
long long ans, a[MAX];
vector<pair<long long, int> > b;
void update(int i) { while(i <= n) f[i]++, i += i & -i; }
int query(int i) {
	int ret = 0;
	while(i > 0) ret += f[i], i -= i & -i;
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> p;
	ans = !p;
	b.emplace_back(0, 0);
	for(int i = 1; i <= n; i++) {
		a[i] += a[i-1] - p;
		b.emplace_back(a[i], i);
	}
	sort(b.begin(), b.end());
	for(auto p: b) {
		if(p.second) {
			ans += query(p.second);
			update(p.second);
		} else update(1);
	}
	cout << ans;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14056 KB Output is correct
2 Correct 0 ms 14056 KB Output is correct
3 Correct 0 ms 14056 KB Output is correct
4 Correct 276 ms 38512 KB Output is correct
5 Correct 173 ms 38512 KB Output is correct
6 Correct 239 ms 38512 KB Output is correct
7 Correct 209 ms 38512 KB Output is correct
8 Correct 209 ms 38512 KB Output is correct
9 Correct 289 ms 38512 KB Output is correct
10 Correct 226 ms 38512 KB Output is correct