제출 #947261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947261		Zena_Hossam	Vudu (COCI15_vudu)	C++14	42 / 140	1056 ms	65536 KiB

vudu

#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 / 140