oj.uz

Submission #165424

# Submission time Handle Problem Language Result Execution time Memory
165424 2019-11-27T07:58:15 Z egekabas Vudu (COCI15_vudu) C++14
0 / 140
 1000 ms 17472 KB 
#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> v1;
vector<pll> v2;
ll sfunc(pll a, pll b){
    return a.ff*b.ss > a.ss*b.ff;
}
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;
    ll cnt = 0;
    v1.clear();
    v2.clear();
    for(ll i = m; i >= l; --i){
        sum += a[i];
        cnt++;
        v1.pb({sum, cnt});
    }
    sum = 0, cnt = 0;
    for(ll i = m+1; i <= r; ++i){
        sum += a[i];
        cnt++;
        v2.pb({sum, cnt});    
    }
    sort(v1.begin(), v1.end(), sfunc);
    sort(v2.begin(), v2.end(), sfunc);
    
    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;
    }

    
}

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

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

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 632 KB Output isn't correct
2 Incorrect 7 ms 632 KB Output isn't correct
3 Incorrect 7 ms 632 KB Output isn't correct
4 Execution timed out 1079 ms 16164 KB Time limit exceeded
5 Incorrect 890 ms 17472 KB Output isn't correct
6 Execution timed out 1077 ms 14792 KB Time limit exceeded
7 Execution timed out 1066 ms 15288 KB Time limit exceeded
8 Execution timed out 1071 ms 13816 KB Time limit exceeded
9 Execution timed out 1078 ms 16408 KB Time limit exceeded
10 Execution timed out 1069 ms 14988 KB Time limit exceeded