Submission #629567

#TimeUsernameProblemLanguageResultExecution timeMemory
629567ElnadyVudu (COCI15_vudu)C++17
42 / 140
955 ms65536 KiB
#include <vector> #include <deque> #include <queue> #include <array> #include <set> #include <string> #include <iostream> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <numeric> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <bitset> #include <climits> #include <unordered_set> #include <unordered_map> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define endl '\n' //#define int long long #define all(pr1) pr1.begin(),pr1.end() #define alr(pr1) pr1.rbegin(),pr1.rend() #define CEIL(pr1, pr2) (pr1 + pr2 - 1) / pr2 #define IOS std::ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define RT(s) return cout<<s,0 #define sz(s) (int)(s.size()) const long long N = 1e5 + 9, M = 3e9 + 9, MOD = 1e9 + 7, OO = 0x3f3f3f3f, MAX = 2147483647, LOO = 0x3f3f3f3f3f3f3f3f; int32_t main() { IOS; int n, m; cin >> n; vector<int> a(n), c, d(n); vector<pair<int, int>> b; map<int, int> mp; for (int i = 0; i < n; i++) cin >> a[i]; cin >> m; a[0] = (a[0] - m); d[0] = a[0]; for (int i = 1; i < n; i++) { a[i] -= m; d[i] = a[i]; a[i] += a[i - 1]; } for (int i = 0; i < n; i++) mp[a[i]]++; for (auto ch : mp) b.push_back({ ch.first, ch.second }); sort(alr(b)); for (int i = 1; i < sz(b); i++) b[i].second += b[i - 1].second; sort(all(b)); for (int i = 0; i < sz(b); i++) c.push_back(b[i].first); tree <pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> st; int cur = 0, ans = 0; for (int i = 0; i < n; i++) { if (c.back() >= cur) { int x = (lower_bound(all(c), cur) - c.begin()); int y = (i - st.order_of_key({ cur, 0 })); ans += (b[x].second - y); } st.insert({ a[i], i }); cur += d[i]; } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...