제출 #380250

#제출 시각아이디문제언어결과실행 시간메모리
380250vishesh312Vudu (COCI15_vudu)C++17
42 / 140
1095 ms50068 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; void solve(int tc) { int n; cin >> n; vector<pair<int, int>> v(n+1); for (int i = 1; i <= n; ++i) { cin >> v[i].first; v[i].second = i; } vector<int> a(n+1); ll p; cin >> p; for (int i = 1; i <= n; ++i) { v[i].first += v[i-1].first - p; } sort(all(v)); 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; } ll ans = 0; ordered_set s; s.insert(a[0]-1); for (int i = 1; i <= n; ++i) { ans += s.order_of_key(a[i]); s.insert(a[i]-1); } 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...