Submission #1230200

#TimeUsernameProblemLanguageResultExecution timeMemory
1230200lechaaVudu (COCI15_vudu)C++20
98 / 140
454 ms74728 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef __gnu_pbds::tree<pair<long long, int>, __gnu_pbds::null_type, less<pair<long long, int>>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> x(n); for(int i = 0; i < n; i++){ cin >> x[i]; } int k; cin >> k; for(int i = 0; i < n; i++){ x[i] -= k; } vector<long long> pref(n+1); ll sum = 0; for(int i = 1; i <= n; i++){ sum += x[i-1]; pref[i] = sum; } sum = 0; ordered_set o; o.insert({0, -1}); for(int i = 0; i < n; i++){ sum += o.order_of_key({pref[i+1], n+1}); o.insert({pref[i+1], i}); } cout << sum << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...