Submission #380262

#TimeUsernameProblemLanguageResultExecution timeMemory
380262vishesh312Vudu (COCI15_vudu)C++17
42 / 140
1102 ms51180 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; #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() const int mod = 1e9+7; struct SegTree { vector<ll> t; int n; SegTree (int _n) { n = _n; t.resize(4*n+1); } void update(int v, int tl, int tr, int val) { if (tl == tr) { t[v]++; } else { int tm = (tl + tr) / 2; if (val <= tm) { update(v*2, tl, tm, val); } else { 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 (r < l) return 0; if (tl == tr) { return t[v]; } int tm = (tl + tr) / 2; return query(v*2, tl, tm, l, min(tm, r)) + query(v*2+1, tm+1, tr, max(tm+1, l), r); } void update(int val) {update(1, 0, n, val);} ll query(int x) {return query(1, 0, n, 0, x);} }; void solve(int tc) { int n; cin >> n; pair<ll, int> v[n+1]; v[0] = {0, 0}; for (int i = 1; i <= n; ++i) { cin >> v[i].first; v[i].second = i; } int a[n+1]; ll p; cin >> p; for (int i = 1; i <= n; ++i) { v[i].first += v[i-1].first - p; } sort(v, v+n+1); ll cur = 0; for (int i = 0; i <= n; ++i) { if (i) if (v[i].first == v[i-1].first) --cur; a[v[i].second] = cur; ++cur; } SegTree seg(n+1); ll ans = 0; seg.update(a[0]); for (int i = 1; i <= n; ++i) { ans += seg.query(a[i]); seg.update(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...