oj.uz

Submission #89963

# Submission time Handle Problem Language Result Execution time Memory
89963 2018-12-19T10:00:41 Z vex Vudu (COCI15_vudu) C++14
140 / 140
 295 ms 24072 KB 
#include <bits/stdc++.h>
#define maxn 1000005
#define plli pair<long long,long long>
using namespace std;
 
long long n;
plli a[maxn];
long long p;
 
long long tree[maxn]={0};
long long manji(long long x)
{
    x--;
    long long sol=0;
    while(x>0)
    {
        sol+=tree[x];
        x-=x&-x;
    }
    return sol;
}
void update(long long x)
{
    while(x<=n)
    {
        tree[x]++;
        x+=x&-x;
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin>>n;
    a[0]={0,0};
    for(int i=0;i<n;i++)
    {
        cin>>a[i+1].first;
        a[i+1].first+=a[i].first;
        a[i+1].second=i+1;
    }
    cin>>p;
 
    for(int i=0;i<=n;i++)
    {
        a[i].first-=p*a[i].second;
    }
  
    sort(a,a+n+1);
    long long sol=0;
 
    for(int i=0;i<=n;i++)a[i].second++;
    for(int i=0;i<=n;i++)
    {
        sol+=manji(a[i].second);
        update(a[i].second);
    }
 
    cout<<sol<<endl;
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Correct 287 ms 23208 KB Output is correct
5 Correct 160 ms 23208 KB Output is correct
6 Correct 253 ms 23208 KB Output is correct
7 Correct 258 ms 23208 KB Output is correct
8 Correct 222 ms 23208 KB Output is correct
9 Correct 295 ms 24072 KB Output is correct
10 Correct 250 ms 24072 KB Output is correct