Submission #622954

#	Time	Username	Problem	Language	Result	Execution time	Memory
622954		3omar_ahmed	Vudu (COCI15_vudu)	C++17	42 / 140	1101 ms	65536 KiB

vudu

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds;

#define int long long
#define endl '\n'
#define ordered_set tree<pair < int ,int >,null_type,less<pair < int ,int >>,rb_tree_tag,tree_order_statistics_node_update>
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()

struct segtree
{
    vector<int> seg1 , seg2;
    int op(int a, int b) {return max(a, b);}
    void build1(int i, int l, int r, vector<int> &a)
    {
        if (l == r) return void(seg1[i] = a[l]);
        build1(i*2, l, (l+r)/2, a), build1(i*2+1, (l+r)/2+1, r, a);
        seg1[i] = op(seg1[i*2], seg1[i*2+1]);
    }
    void build2(int i, int l, int r, vector<int> &a)
    {
        if (l == r) return void(seg2[i] = a[l]);
        build2(i*2, l, (l+r)/2, a), build2(i*2+1, (l+r)/2+1, r, a);
        seg2[i] = min(seg2[i*2], seg2[i*2+1]);
    }
    int get(int i, int l, int r, int s, int e , int val )
    {
        if (r < s || e < l) return 0;
        if (s <= l && r <= e && val >= seg1[i]) return r - l + 1 ;
        if (s <= l && r <= e && val < seg2[i]) return 0 ;
        return get(i*2, l, (l+r)/2, s, e, val ) + get(i*2+1, (l+r)/2+1, r, s, e , val);
    }
    segtree(vector<int> &a) {seg1.resize(4*a.size()), seg2.resize(4*a.size()), build1(1, 0, a.size()-1, a),build2(1, 0, a.size()-1, a);}
};
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0);

    int n ;
    cin >> n;
    vector < int > a(n);
    for(auto &i : a) cin >> i ;
    int x;
    cin >> x;
    for(auto &i : a) i -= x ;
    vector < int > pre(n);
    for( int i = 0 ; i < n ; i++ )
        pre[i] = pre[( i - 1 == -1 ? 0 : i - 1)] + a[i];
    int ans = 0 ;
    segtree seg(pre);
    /*for( auto i : seg.seg1 ) cout << i << ' ';
    cout <<endl ;
    for( auto i : seg.seg2 ) cout << i << ' ';
    cout <<endl ;*/
    for( int i = 0 ; i < n ; i ++ ){
        int val = seg.get(1,0,n-1,0,i-(pre[i] < 0),pre[i]);
        ans += val;
        //cout << val << endl ;
    }
    cout << ans << endl;
    return 0 ;
}

• Subtask 1: 42 / 140