# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
462602 |
2021-08-10T22:36:42 Z |
Hamed5001 |
Vudu (COCI15_vudu) |
C++14 |
|
1000 ms |
58996 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int, int> ID;
int id = 1;
const int mxN = 1e6+100;
int BIT[mxN];
void add(int idx, int delta) {
for (; idx < id; idx += idx & -idx)
BIT[idx] += delta;
}
int query(int idx) {
int ret = 0;
for (; idx > 0; idx -= idx & -idx)
ret += BIT[idx];
return ret;
}
void solve() {
int N, P;
cin >> N;
vector<int> A(N); for (auto& a : A) cin >> a;
cin >> P;
for (auto& a : A) a-=P;
vector<int> AA;
int sum = 0;
for (auto a : A) {
sum += a;
AA.push_back(sum);
}
sort(AA.rbegin(), AA.rend());
ID[0] = id++;
for (int i = 0; i < AA.size(); ++i) {
if (!ID[AA[i]])
ID[AA[i]] = id++;
}
for (auto aa : AA) {
add(ID[aa], 1);
}
// cout << query(3) << endl;
// for (auto& [a, b] : ID) {
// cout << a << ' ' << b << endl;
// }
sum = 0;
ll ans = 0;
for (auto a : A) {
int sumid = ID[sum];
ans += query(sumid);
sum += a;
add(sumid, -1);
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < AA.size(); ++i) {
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
716 KB |
Output isn't correct |
2 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
3 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
4 |
Execution timed out |
1093 ms |
57016 KB |
Time limit exceeded |
5 |
Incorrect |
901 ms |
32408 KB |
Output isn't correct |
6 |
Execution timed out |
1090 ms |
50468 KB |
Time limit exceeded |
7 |
Execution timed out |
1100 ms |
52548 KB |
Time limit exceeded |
8 |
Execution timed out |
1094 ms |
45608 KB |
Time limit exceeded |
9 |
Execution timed out |
1062 ms |
58996 KB |
Time limit exceeded |
10 |
Execution timed out |
1098 ms |
51188 KB |
Time limit exceeded |