# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
463686 |
2021-08-11T13:41:16 Z |
Hamed5001 |
Vudu (COCI15_vudu) |
C++14 |
|
701 ms |
65540 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll, ll> ID;
const int mxN = 1e6+100;
ll BIT[mxN], N, P, id = 1;
void add(int idx, ll delta) {
for (; idx < id; idx += idx & -idx)
BIT[idx] += delta;
}
ll query(int idx) {
ll ret = 0;
for (; idx > 0; idx -= idx & -idx)
ret += BIT[idx];
return ret;
}
void solve() {
cin >> N;
vector<ll> A(N);
for (auto& a : A) scanf("%lld", &a);
cin >> P;
for (auto& a : A) a-=P;
vector<ll> AA;
ll sum = 0;
AA.push_back(sum);
for (auto& a : A) {
sum += a;
AA.push_back(sum);
}
sort(AA.rbegin(), AA.rend());
for (int i = 0; i < AA.size(); ++i) {
if (!ID[AA[i]])
ID[AA[i]] = id++;
}
for (auto& aa : AA) {
add(ID[aa], 1);
}
add(ID[0], -1);
sum = 0;
ll ans = 0;
for (auto a : A) {
ans += query(ID[sum]);
sum += a;
add(ID[sum], -1);
}
printf("%lld", ans);
}
int main() {
solve();
}
Compilation message
vudu.cpp: In function 'void solve()':
vudu.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < AA.size(); ++i) {
| ~~^~~~~~~~~~~
vudu.cpp:25:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | for (auto& a : A) scanf("%lld", &a);
| ~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
844 KB |
Output is correct |
2 |
Correct |
4 ms |
716 KB |
Output is correct |
3 |
Correct |
4 ms |
716 KB |
Output is correct |
4 |
Runtime error |
543 ms |
65540 KB |
Execution killed with signal 9 |
5 |
Correct |
701 ms |
47284 KB |
Output is correct |
6 |
Runtime error |
532 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Runtime error |
527 ms |
65540 KB |
Execution killed with signal 9 |
8 |
Runtime error |
565 ms |
65540 KB |
Execution killed with signal 9 |
9 |
Runtime error |
547 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
598 ms |
65540 KB |
Execution killed with signal 9 |