# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
75552 | noclever | Vudu (COCI15_vudu) | C++14 | 413 ms | 23928 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
template<typename T>
class fenwick {
private:
int n;
vector<T> fenw;
public:
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<long long> a(n);
vector<long long> b(n);
vector<int> mp(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long p;
cin >> p;
for (int i = 0; i < n; i++) {
a[i] -= p;
}
b[0] = a[0];
for (int i = 1; i < n; i++) {
a[i] += a[i - 1];
b[i] = a[i];
}
sort(b.begin(), b.end());
for (int i = 0; i < n; i++) {
mp[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}
fenwick<int> fenw(n);
long long ans = 0ll;
for (int i = 0; i < n; i++) {
if (a[i] >= 0) {
ans++;
}
int tmp = mp[i];
ans += (fenw.get(tmp));
fenw.modify(tmp, +1);
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |