# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
648970 | tvladm2009 | Vudu (COCI15_vudu) | C++14 | 521 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, std::less<T>, rb_tree_tag,tree_order_statistics_node_update>;
using ll = long long;
#define int ll
int const nmax = 1000000;
int v[5 + nmax], sp[5 + nmax];
signed main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int n, p;
std::cin >> n;
for(int i = 1;i <= n; i++)
std::cin >> v[i];
std::cin >> p;
for(int i = 1;i <= n; i++) {
v[i] -= p;
sp[i] = sp[i - 1] + v[i];
}
oset<int> s;
s.insert(0);
int ans = 0;
for(int i = 1;i <= n; i++) {
ans += s.order_of_key(sp[i]);
s.insert(sp[i]);
}
std::map<int, int> mp;
mp[0]++;
for(int i = 1;i <= n; i++) {
ans += mp[sp[i]];
mp[sp[i]]++;
}
std::cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |