Submission #582572

#	Time	Username	Problem	Language	Result	Execution time	Memory
582572		vuavisao	Vudu (COCI15_vudu)	C++14	140 / 140	387 ms	52940 KiB

vudu

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const int N = 1e6 + 10;

struct state
{
    ll val;
    int idx;

    state() {};
    state(ll val, int idx) : val(val), idx(idx) {};

    bool operator < (const state & other) const
    {
        return this -> val < other.val;
    }
};

struct FenWick
{
    int MaxVal;
    vector<int> tree;

    FenWick()
    {
        MaxVal = 0;
    };

    void init(int n)
    {
        MaxVal = n;
        tree.resize(n + 1, 0);
    }

    void Update(int idx, int val)
    {
        while(idx <= MaxVal)
        {
            tree[idx] += val;
            idx += (idx & - idx);
        }
    }

    int Query(int idx)
    {
        int s = 0;
        while(idx > 0)
        {
            s += tree[idx];
            idx -= (idx & - idx);
        }
        return s;
    }

    int Sum_to(int lhs, int rhs)
    {
        if(lhs > rhs) return 0;
        return Query(rhs) - Query(lhs - 1);
    }
};


int n;
ll limit;

ll s[N];

state a[N];
state memo[N];

ll res;

void pre_process()
{
    for(int i = 1; i <= n; i++)
    {
        a[i] = state(s[i - 1] - limit * i + limit, i);
        memo[i] = state(s[i] - limit * i, i);
    }
    sort(a + 1, a + 1 + n);
    sort(memo + 1, memo + 1 + n);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("Vudu.inp", "r", stdin);
//    freopen("Vudu.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int a; cin >> a;
        s[i] = s[i - 1] + a;
    }
    cin >> limit;
    pre_process();
    FenWick bit;
    bit.init(n);
    for(int i = 1, j = 1; i <= n; i++)
    {
        while(j <= n && a[j].val <= memo[i].val) bit.Update(a[j].idx, 1), j++;
        res += bit.Query(memo[i].idx);
    }
    cout << res;
    return 0;
}

/// Code by vuavisao

• Subtask 1: 140 / 140