oj.uz

Submission #165431

# Submission time Handle Problem Language Result Execution time Memory
165431 2019-11-27T08:27:38 Z egekabas Vudu (COCI15_vudu) C++14
112 / 140
 1000 ms 16532 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<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() {
    
    //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

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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Execution timed out 1084 ms 16216 KB Time limit exceeded
5 Correct 596 ms 11212 KB Output is correct
6 Correct 969 ms 14836 KB Output is correct
7 Correct 997 ms 15476 KB Output is correct
8 Correct 852 ms 13772 KB Output is correct
9 Execution timed out 1077 ms 16532 KB Time limit exceeded
10 Correct 980 ms 14852 KB Output is correct