Submission #443390

#TimeUsernameProblemLanguageResultExecution timeMemory
443390arujbansalVudu (COCI15_vudu)C++17
140 / 140
383 ms23904 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() #define int long long const int MXN = 1e5 + 5, INF = 1e9 + 5; void solve() { int N; cin >> N; vector<int> A(N); for (auto &x : A) cin >> x; int P; cin >> P; vector<int> compress; compress.push_back(0); int sum = 0; for (const auto &x : A) { sum += x - P; compress.push_back(sum); } sort(all(compress)); compress.resize(unique(all(compress)) - compress.begin()); vector<int> fenwick(N + 5, 0); for (int i = lower_bound(all(compress), 0) - compress.begin() + 1; i <= N + 2; i += i & -i) fenwick[i]++; int ans = 0; sum = 0; for (const auto &x : A) { sum += x - P; int sum_pos = lower_bound(all(compress), sum) - compress.begin() + 1; for (int i = sum_pos; i > 0; i -= i & -i) ans += fenwick[i]; for (int i = sum_pos; i <= N + 2; i += i & -i) fenwick[i]++; } cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...