Submission #445501

#	Time	Username	Problem	Language	Result	Execution time	Memory
445501		ak2006	Vudu (COCI15_vudu)	C++14	140 / 140	461 ms	65536 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
struct BIT
{
    int n;
    vl bit;
    BIT(int _n)
    {
        n = _n;
        bit.assign(n + 10,0);
    }
    void update(int i,ll inc)
    {
        for (;i<=n;i+=i&(-i))bit[i] += inc;
    }
    ll sum(int i)
    {
        ll ret = 0;
        for (;i>0;i-=i&(-i))ret += bit[i];
        return ret;
    }
};
int main()
{
    setIO();
    ll n,p;
    cin>>n;
    vvl a(n + 1,vl(2));
    for (int i = 1;i<=n;i++)cin>>a[i][0],a[i][1] = i;
    cin>>p;
    for (int i = 1;i<=n;i++)a[i][0] = a[i - 1][0] + a[i][0] - p;

    sort(a.begin() + 1,a.end());

    BIT val(n);
    ll out = 0;
    for (int i = 1;i<=n;i++){
        ll now = val.sum(a[i][1] - 1);
        out += now;
        val.update(a[i][1],1);
        if (a[i][0] >= 0)out++;
    }
    cout<<out;
    return 0;
}

• Subtask 1: 140 / 140