Submission #165428

#	Time	Username	Problem	Language	Result	Execution time	Memory
165428		egekabas	Vudu (COCI15_vudu)	C++14	112 / 140	1077 ms	16464 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<ll> v1, v2;
void calc(ll l, ll r){
    if(l == r){
        if(a[l] >= p)
            ++ans;
        return;
    }
    ll m = (l+r)/2;
    calc(l, m);
    calc(m+1, r);
    ll sum = 0;
    v1.clear();
    v2.clear();
    for(ll i = m; i >= l; --i){
        sum += a[i]-p;
        v1.pb(sum);
    }
    sum = 0;
    for(ll i = m+1; i <= r; ++i){
        sum += a[i]-p;
        v2.pb(sum);    
    }
    sort(v1.begin(), v1.end(), greater<ll>());
    sort(v2.begin(), v2.end(), greater<ll>());
    
    ll j = v2.size()-1;
    for(ll i = 0; i < v1.size(); ++i){
        for(; j >= 0; --j)
            if(v1[i]+v2[j] >= 0)
                break;
        ans += j+1;
    }    
}
    
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);
    cout << ans << "\n";
}

Compilation message (stderr)

vudu.cpp: In function 'void calc(ll, ll)':
vudu.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < v1.size(); ++i){
                   ~~^~~~~~~~~~~

• Subtask 1: 112 / 140