Submission #380272

#TimeUsernameProblemLanguageResultExecution timeMemory
380272vishesh312Vudu (COCI15_vudu)C++17
140 / 140
776 ms59196 KiB
#include "bits/stdc++.h" using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using ordered_set = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>; */ #define all(x) begin(x), end(x) #define sz(x) (int)x.size() using ll = long long; const int mod = 1e9+7; int mx = 1e6+5; const int segsz = mx*4; struct SegTree { vector<ll> t; void update(int v, int tl, int tr, int val) { if (tl > val or tr < val) return; if (tl == tr) { t[v]++; } else { int tm = (tl + tr) / 2; update(v*2, tl, tm, val); update(v*2+1, tm+1, tr, val); t[v] = t[v*2] + t[v*2+1]; } } ll query(int v, int tl, int tr, int l, int r) { if (l > tr or r < tl) return 0; if (tl >= l and tr <= r) { return t[v]; } int tm = (tl + tr) / 2; return query(v*2, tl, tm, l, r) + query(v*2+1, tm+1, tr, l, r); } SegTree() {t.resize(segsz);} void update(int n, int val) {update(1, 0, n, val);} ll query(int n, int val) {return query(1, 0, n, 0, val);} } seg; void solve(int tc) { int n; cin >> n; ll v[n+1]; for (int i = 1; i <= n; ++i) { cin >> v[i]; } int a[n+1]; ll p; cin >> p; vector<array<ll, 2>> vx; ll sum = 0; vx.push_back({0,0}); for (int i = 1; i <= n; ++i) { sum += (v[i] - p); vx.push_back({sum, i}); } sort(all(vx)); ll cur = 0; for (int i = 0; i < sz(vx); ++i) { if (i) if (vx[i][0] == vx[i-1][0]) --cur; a[vx[i][1]] = cur; ++cur; } ll ans = 0; seg.update(n, a[0]); for (int i = 1; i <= n; ++i) { ans += seg.query(n, a[i]); seg.update(n, a[i]); } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc = 1; //cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...