oj.uz

Submission #947261

# Submission time Handle Problem Language Result Execution time Memory
947261 2024-03-15T19:36:21 Z Zena_Hossam Vudu (COCI15_vudu) C++14
42 / 140
 1000 ms 65536 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
namespace __gnu_pbds{
          typedef tree<int,
                       null_type,
                       less_equal<int>,
                       rb_tree_tag,
                       tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define ll double
#define ll long long
//#define ll1 int
#define F first
#define S second
#define sz size()
#define all(s) s.begin(),s.end()
#define all1(s) s.rbegin(),s.rend()
int main()
{
    //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout);
    ll T=1;
    fi
    //cin>>T;ll oo=0;
    while(T--)
    {
       ll n;
       cin>>n;
       ll arr[n];
       for(ll i=0;i<n;i++){
        cin>>arr[i];
       }
       ll x;
       cin>>x;
       ll a[n]={};ordered_set s,v;
       for(ll i=0;i<n;i++){
        a[i]+=(arr[i]-x);
        if(i)a[i]+=a[i-1];
        if(a[i]>=0){
        s.insert(a[i]);
        }
        else v.insert(a[i]);
       }ll c=0;
       for(ll i=0;i<n;i++){
        ll k=0;if(i)k=a[i-1];
        if(k>0){
            ll p=s.order_of_key(k);
            c+=(s.size()-p);
        }
        else if(k<0){
            ll p=v.size()-v.order_of_key(k);
            c+=(s.size()+p);
        }else c+=s.size();
        if(a[i]>=0){
            s.erase(s.upper_bound(a[i]));
        }else  v.erase(v.upper_bound(a[i]));
       }cout<<c;
    }
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 720 KB Output is correct
4 Execution timed out 1035 ms 65536 KB Time limit exceeded
5 Incorrect 534 ms 39848 KB Output isn't correct
6 Incorrect 992 ms 62260 KB Output isn't correct
7 Execution timed out 1010 ms 64592 KB Time limit exceeded
8 Execution timed out 1055 ms 55964 KB Time limit exceeded
9 Execution timed out 1050 ms 65536 KB Time limit exceeded
10 Execution timed out 1056 ms 63060 KB Time limit exceeded