# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
718800 | Doncho_Bonboncho | Vudu (COCI15_vudu) | C++14 | 255 ms | 45248 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX_N = 1e6 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;
ll pref[MAX_N];
std::vector<std::pair<ll, int>> v;
int ind[MAX_N];
ll fen[MAX_N];
ll query( int x ){
//std::cerr<<" query "<<x<<"\n";
ll nas = 0;
while( x ){
nas += fen[x];
x -= x&-x;
}
return nas;
}
void update( int x ){
//std::cerr<<" update "<<x<<"\n";
while( x <= MAX_N ){
fen[x] ++;
x += x&-x;
}
}
int main () {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int n;
std::cin>>n;
for( int i=1 ; i<=n ; i++ ) std::cin>>pref[i];
int k;
std::cin>>k;
for( int i=1 ; i<=n ; i++ ){
pref[i] += pref[i-1] - k;
v.push_back({pref[i], i});
}
v.push_back({0, 0});
std::sort( v.begin(), v.end() );
for( int i=0 ; i<=n ; i++ ) ind[v[i].second] = i +1;
ll nas = 0;
for( int i=0 ; i<=n ; i++ ){
nas += query( ind[i] );
update(ind[i]);
}
std::cout<<nas<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |