# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924101 | 2024-02-08T13:03:13 Z | TIN | Vudu (COCI15_vudu) | C++17 | 500 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; ll a[N]; ll P; ll sum; vector<ll> p; ll ans = 0; 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]++; } ll get(int i) const { 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; } void Solve() { //Your Code cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cin >> P; sum = 0; p.push_back(sum); for (int i = 1; i <= n; i++) { sum += a[i] - P; p.push_back(sum); } compress(p); Fenwick BIT(sz(p) + 1); for (int i = 1; i <= n; i++) { BIT.set(p[i - 1]); ans += BIT.get(p[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 | 860 KB | Output is correct |
4 | Runtime error | 366 ms | 65536 KB | Execution killed with signal 9 |
5 | Correct | 293 ms | 47816 KB | Output is correct |
6 | Correct | 467 ms | 65536 KB | Output is correct |
7 | Correct | 457 ms | 65536 KB | Output is correct |
8 | Correct | 431 ms | 63844 KB | Output is correct |
9 | Runtime error | 309 ms | 65536 KB | Execution killed with signal 9 |
10 | Correct | 500 ms | 65536 KB | Output is correct |