# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
380263 |
2021-03-20T18:23:30 Z |
vishesh312 |
Vudu (COCI15_vudu) |
C++17 |
|
1000 ms |
51180 KB |
#pragma GCC optimize("unroll-loops", "Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
const int mod = 1e9+7;
struct SegTree {
vector<ll> t;
int n;
SegTree (int _n) {
n = _n;
t.resize(4*n+1);
}
void update(int v, int tl, int tr, int val) {
if (tl == tr) {
t[v]++;
} else {
int tm = (tl + tr) / 2;
if (val <= tm) {
update(v*2, tl, tm, val);
} else {
update(v*2+1, tm+1, tr, val);
}
t[v] = t[v*2] + t[v*2+1];
}
}
ll query(int v, int tl, int tr, int l, int r) {
if (r < l) return 0;
if (tl == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return query(v*2, tl, tm, l, min(tm, r)) + query(v*2+1, tm+1, tr, max(tm+1, l), r);
}
void update(int val) {update(1, 0, n, val);}
ll query(int x) {return query(1, 0, n, 0, x);}
};
void solve(int tc) {
int n;
cin >> n;
pair<ll, int> v[n+1];
v[0] = {0, 0};
for (int i = 1; i <= n; ++i) {
cin >> v[i].first;
v[i].second = i;
}
int a[n+1];
ll p;
cin >> p;
for (int i = 1; i <= n; ++i) {
v[i].first += v[i-1].first - p;
}
sort(v, v+n+1);
ll cur = 0;
for (int i = 0; i <= n; ++i) {
if (i) if (v[i].first == v[i-1].first) --cur;
a[v[i].second] = cur;
++cur;
}
SegTree seg(n+1);
ll ans = 0;
seg.update(a[0]);
for (int i = 1; i <= n; ++i) {
ans += seg.query(a[i]);
seg.update(a[i]);
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
748 KB |
Output is correct |
2 |
Correct |
104 ms |
620 KB |
Output is correct |
3 |
Correct |
104 ms |
620 KB |
Output is correct |
4 |
Execution timed out |
1087 ms |
49516 KB |
Time limit exceeded |
5 |
Execution timed out |
1050 ms |
28140 KB |
Time limit exceeded |
6 |
Execution timed out |
1097 ms |
43884 KB |
Time limit exceeded |
7 |
Execution timed out |
1099 ms |
45676 KB |
Time limit exceeded |
8 |
Execution timed out |
1095 ms |
39532 KB |
Time limit exceeded |
9 |
Execution timed out |
1091 ms |
51180 KB |
Time limit exceeded |
10 |
Execution timed out |
1054 ms |
44524 KB |
Time limit exceeded |