# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1030337 | 2024-07-22T02:54:56 Z | TIN | Vudu (COCI15_vudu) | C++17 | 468 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; #define FNAME "test" typedef long long ll; const int N = 1e6 + 5; int n; vector<ll> a; ll P; vector<ll> pre; ll mx; ll ans; struct Fenwick { int n; vector<ll> f; Fenwick(int _n) { n = _n; f.resize(n + 2, 0LL); } void set(int i) { for (; i <= n; i += i & (-i)) f[i]++; } ll get(int i) { ll r = 0; for (; i > 0; 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(v.begin(), v.end()); vector<ll> b(s.begin(), s.end()); mx = (int) b.size() + 1; for (ll &x : v) x = lower_bound(b.begin(), b.end(), 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(n); 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 | 3 ms | 860 KB | Output is correct |
2 | Correct | 2 ms | 860 KB | Output is correct |
3 | Correct | 2 ms | 772 KB | Output is correct |
4 | Runtime error | 352 ms | 65536 KB | Execution killed with signal 9 |
5 | Correct | 293 ms | 44116 KB | Output is correct |
6 | Incorrect | 458 ms | 65536 KB | Output isn't correct |
7 | Correct | 452 ms | 65536 KB | Output is correct |
8 | Correct | 389 ms | 62040 KB | Output is correct |
9 | Runtime error | 322 ms | 65536 KB | Execution killed with signal 9 |
10 | Correct | 468 ms | 65536 KB | Output is correct |