Submission #165430

#	Time	Username	Problem	Language	Result	Execution time	Memory
165430		egekabas	Vudu (COCI15_vudu)	C++14	70 / 140	1079 ms	16588 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;
inline 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() {
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%lld", &n);
    for(ll i = 0; i < n; ++i){
        scanf("%lld", &a[i]);
    }
    cin >> p;
    scanf("%lld", &p);
    calc(0, n-1);
    printf("%lld", ans);
}

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){
                   ~~^~~~~~~~~~~
vudu.cpp: In function 'int main()':
vudu.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
vudu.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
         ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &p);
     ~~~~~^~~~~~~~~~~~

• Subtask 1: 70 / 140