# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924121 | 2024-02-08T13:27:55 Z | TIN | Vudu (COCI15_vudu) | C++17 | 454 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; #define FNAME "test" #define sz(v) (int) (v).size() #define all(v) (v).begin(), (v).end() typedef long long ll; const int N = 1e6 + 5; int n; vector<ll> a; ll P; vector<ll> pre; ll ans; struct Fenwick { int n; vector<ll> f; Fenwick(int n) : n(n), f(n + 1, 0) {} void set(int i) { for (; i <= n; i += i & (-i)) f[i]++; return; } ll get(int i) { ll r = 0; for (; i >= 1; i -= i & (-i)) r += f[i]; return r; } }; void Task() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout << fixed << setprecision(9); if (fopen(FNAME".inp","r")) { freopen(FNAME".inp","r",stdin); freopen(FNAME".out","w",stdout); } } void compress(vector<ll>& v) { set<ll> s(all(v)); vector<ll> b(all(s)); for (ll &x : v) x = lower_bound(all(b), x) - b.begin() + 1; return; } void Solve() { //Your Code cin >> n; a.resize(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; cin >> P; pre.resize(n + 1); pre[0] = 0; for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (a[i] - P); compress(pre); Fenwick BIT(sz(pre) + 1); ans = 0; for (int i = 1; i <= n; i++) { BIT.set(pre[i - 1]); ans += BIT.get(pre[i]); } cout << ans << '\n'; return; } int main() { Task(); Solve(); cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms"; return 37^37; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 860 KB | Output is correct |
2 | Correct | 2 ms | 604 KB | Output is correct |
3 | Correct | 2 ms | 604 KB | Output is correct |
4 | Runtime error | 358 ms | 65536 KB | Execution killed with signal 9 |
5 | Correct | 284 ms | 38992 KB | Output is correct |
6 | Correct | 452 ms | 60496 KB | Output is correct |
7 | Correct | 454 ms | 65536 KB | Output is correct |
8 | Correct | 397 ms | 54608 KB | Output is correct |
9 | Runtime error | 297 ms | 65536 KB | Execution killed with signal 9 |
10 | Correct | 448 ms | 62292 KB | Output is correct |