# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924116 | 2024-02-08T13:21:05 Z | TIN | Vudu (COCI15_vudu) | C++17 | 489 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(ll i) { for (; i <= n; i += i & (-i)) f[i]++; return; } ll get(ll 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>& a) { set<ll> s(a.begin(), a.end()); vector<ll> b(s.begin(), s.end()); for (ll &x : a) 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(sz(pre)); ans = 0; for (int i = 1; i <= n; i++) { BIT.set(pre[i - 1]); ans += BIT.get(pre[i]); } cout << ans << '\n'; } 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 | 604 KB | Output is correct |
4 | Runtime error | 398 ms | 65536 KB | Execution killed with signal 9 |
5 | Correct | 282 ms | 41672 KB | Output is correct |
6 | Correct | 484 ms | 65500 KB | Output is correct |
7 | Correct | 489 ms | 65536 KB | Output is correct |
8 | Correct | 429 ms | 58684 KB | Output is correct |
9 | Runtime error | 351 ms | 65536 KB | Execution killed with signal 9 |
10 | Correct | 450 ms | 65536 KB | Output is correct |