# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
380592 |
2021-03-22T12:21:02 Z |
Aryan_Raina |
Vudu (COCI15_vudu) |
C++14 |
|
542 ms |
65540 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e17;
const int MOD = 1e9;
struct SegTree {
int size;
vector<int> values;
void init(int n) {
size = 1;
while (size < n) size <<= 1;
values.resize(2*size);
}
int sum(int l, int r, int x, int lx, int rx) {
if (lx >= r || l >= rx) return 0;
if (l <= lx && rx <= r) return values[x];
int m = (lx + rx) >> 1;
int s1 = sum(l, r, 2*x+1, lx, m);
int s2 = sum(l, r, 2*x+2, m, rx);
return s1+s2;
}
int sum(int l, int r) {
return sum(l, r, 0, 0, size);
}
void update(int i, int x, int lx, int rx) {
if (rx - lx == 1) return void(values[x]++);
int m = (lx + rx) >> 1;
if (i < m) update(i, 2*x+1, lx, m);
else update(i, 2*x+2, m, rx);
values[x] = values[2*x+1] + values[2*x+2];
}
void update(int i) {
update(i, 0, 0, size);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
vector<int> a(n), tmp(n+1);
for (int &i : a) cin>>i;
int p; cin>>p;
int psum = 0;
for (int i = 0; i < n; i++) psum += a[i], tmp[i] = a[i] - (i+1)*p;
tmp[n] = 0;
sort(tmp.begin(), tmp.end());
map<int, int> mp; int cnt = 0;
for (int i : tmp) if (!mp.count(i)) mp[i] = cnt++;
SegTree st; st.init(cnt);
st.update(mp[0]);
int ans = 0; psum = 0;
for (int i = 0; i < n; i++) {
psum += a[i];
int diff = psum - (i+1)*p;
ans += st.sum(mp[tmp[0]], mp[diff]+1);
st.update(mp[diff]);
}
cout<<ans<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
1516 KB |
Output isn't correct |
2 |
Incorrect |
6 ms |
1260 KB |
Output isn't correct |
3 |
Incorrect |
6 ms |
1388 KB |
Output isn't correct |
4 |
Runtime error |
454 ms |
65540 KB |
Execution killed with signal 9 |
5 |
Runtime error |
372 ms |
65540 KB |
Execution killed with signal 9 |
6 |
Runtime error |
542 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Runtime error |
452 ms |
65540 KB |
Execution killed with signal 9 |
8 |
Runtime error |
439 ms |
65540 KB |
Execution killed with signal 9 |
9 |
Runtime error |
464 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
447 ms |
65536 KB |
Execution killed with signal 9 |