Submission #165426

#	Time	Username	Problem	Language	Result	Execution time	Memory
165426		egekabas	Vudu (COCI15_vudu)	C++14	0 / 140	64 ms	65540 KiB

vudu

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n, p;
ll ans = 0;
ll a[1000009];
vector<pll> pre[4000009];
vector<pll> suf[4000009];
ll sfunc(pll a, pll b){
    return a.ff*b.ss > a.ss*b.ff;
}
void calc(ll l, ll r, ll id){
    if(l == r){
        if(a[l] >= p)
            ++ans;
        pre[id] = suf[id] = {{a[l], 1}};
        return;
    }
    ll m = (l+r)/2;
    calc(l, m, 2*id);
    calc(m+1, r, 2*id+1);
    vector<pll> &v1 = suf[2*id];
    vector<pll> &v2 = pre[2*id+1];
    ll j = v2.size()-1;
    for(ll i = 0; i < v1.size(); ++i){
        for(; j >= 0; --j)
            if(v1[i].ff+v2[j].ff >= p*(v1[i].ss+v2[j].ss))
                break;
        ans += j+1;
    }
    ll sum = 0, cnt = 0;
    for(ll i = l; i <= m; ++i){
        ++cnt;
        sum += a[i];
    }
    for(ll i = 0; i < pre[2*id+1].size(); ++i){
        pre[2*id+1][i].ff += sum;
        pre[2*id+1][i].ss += cnt;
    }
    sum = 0, cnt = 0;
    for(ll i = m+1; i <= r; ++i){
        ++cnt;
        sum += a[i];
    }
    for(ll i = 0; i < suf[2*id].size(); ++i){
        suf[2*id][i].ff += sum;
        suf[2*id][i].ss += cnt;
    }
    ll i = 0; j = 0;
    while(i < pre[2*id].size() || j < pre[2*id+1].size()){
        if(i == pre[2*id].size()){
            pre[id].pb(pre[2*id+1][j]);
            ++j;
        }
        else if(j == pre[2*id+1].size()){
            pre[id].pb(pre[2*id][i]);
            ++i;
        }
        else if(sfunc(pre[2*id][i], pre[2*id+1][j])){
            pre[id].pb(pre[2*id][i]);
            ++i;
        }
        else{
            pre[id].pb(pre[2*id+1][j]);
            ++j;
        }
    }
    i = 0, j = 0;
    while(i < suf[2*id].size() || j < suf[2*id+1].size()){
        if(i == suf[2*id].size()){
            suf[id].pb(suf[2*id+1][j]);
            ++j;
        }
        else if(j == suf[2*id+1].size()){
            suf[id].pb(suf[2*id][i]);
            ++i;
        }
        else if(sfunc(suf[2*id][i], suf[2*id+1][j])){
            suf[id].pb(suf[2*id][i]);
            ++i;
        }
        else{
            suf[id].pb(suf[2*id+1][j]);
            ++j;
        }
    }
    pre[2*id].clear();
    suf[2*id].clear();
    pre[2*id+1].clear();
    suf[2*id+1].clear();
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    for(ll i = 0; i < n; ++i){
        cin >> a[i];
    }
    cin >> p;
    calc(0, n-1, 1);
    cout << ans << "\n";
}

Compilation message (stderr)

vudu.cpp: In function 'void calc(ll, ll, ll)':
vudu.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < v1.size(); ++i){
                   ~~^~~~~~~~~~~
vudu.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < pre[2*id+1].size(); ++i){
                   ~~^~~~~~~~~~~~~~~~~~~~
vudu.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < suf[2*id].size(); ++i){
                   ~~^~~~~~~~~~~~~~~~~~
vudu.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < pre[2*id].size() || j < pre[2*id+1].size()){
           ~~^~~~~~~~~~~~~~~~~~
vudu.cpp:60:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < pre[2*id].size() || j < pre[2*id+1].size()){
                                   ~~^~~~~~~~~~~~~~~~~~~~
vudu.cpp:61:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == pre[2*id].size()){
            ~~^~~~~~~~~~~~~~~~~~~
vudu.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(j == pre[2*id+1].size()){
                 ~~^~~~~~~~~~~~~~~~~~~~~
vudu.cpp:79:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < suf[2*id].size() || j < suf[2*id+1].size()){
           ~~^~~~~~~~~~~~~~~~~~
vudu.cpp:79:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < suf[2*id].size() || j < suf[2*id+1].size()){
                                   ~~^~~~~~~~~~~~~~~~~~~~
vudu.cpp:80:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == suf[2*id].size()){
            ~~^~~~~~~~~~~~~~~~~~~
vudu.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(j == suf[2*id+1].size()){
                 ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 140