oj.uz

답안 #26673

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

int n, p, a[MAX], f[MAX];
long long ans, sum[MAX];
map<long long, int> pos;
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;
	vector<long long> tmp;
	tmp.push_back(0);
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + a[i] - p;
		tmp.push_back(sum[i]);
	}
	sort(tmp.begin(), tmp.end());
	tmp.resize(distance(tmp.begin(), unique(tmp.begin(), tmp.end())));
	for(int i = 0; i < tmp.size(); i++) pos[tmp[i]] = i+1;
	update(pos[0]);
	for(int i = 1; i <= n; i++) {
		ans += query(pos[sum[i]]);
		update(pos[sum[i]]);
	}
	cout << ans;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tmp.size(); i++) pos[tmp[i]] = i+1;
                   ^

Subtask #1
56.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18236 KB Output is correct
2 Correct 3 ms 18236 KB Output is correct
3 Correct 3 ms 18104 KB Output is correct
4 Memory limit exceeded 409 ms 65536 KB Memory limit exceeded
5 Correct 729 ms 60096 KB Output is correct
6 Memory limit exceeded 413 ms 65536 KB Memory limit exceeded
7 Memory limit exceeded 409 ms 65536 KB Memory limit exceeded
8 Memory limit exceeded 336 ms 65536 KB Memory limit exceeded
9 Memory limit exceeded 449 ms 65536 KB Memory limit exceeded
10 Memory limit exceeded 366 ms 65536 KB Memory limit exceeded