oj.uz

Submission #622951

# Submission time Handle Problem Language Result Execution time Memory
622951 2022-08-04T21:19:16 Z 3omar_ahmed Vudu (COCI15_vudu) C++17
42 / 140
 1000 ms 47176 KB 
#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> seg;
    int op(int a, int b) {return max(a, b);}
    void build(int i, int l, int r, vector<int> &a)
    {
        if (l == r) return void(seg[i] = a[l]);
        build(i*2, l, (l+r)/2, a), build(i*2+1, (l+r)/2+1, r, a);
        seg[i] = op(seg[i*2], seg[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 >= seg[i]) return r - l + 1 ;
        if( l == r ) 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) {seg.resize(4*a.size()), build(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 : pre)cout<<i<<' ';
    cout<<endl;
    for( auto i : seg.seg ) 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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 596 KB Output is correct
2 Correct 33 ms 596 KB Output is correct
3 Correct 42 ms 596 KB Output is correct
4 Execution timed out 1090 ms 45652 KB Time limit exceeded
5 Execution timed out 1099 ms 25932 KB Time limit exceeded
6 Execution timed out 1086 ms 40416 KB Time limit exceeded
7 Execution timed out 1082 ms 42008 KB Time limit exceeded
8 Execution timed out 1083 ms 36440 KB Time limit exceeded
9 Execution timed out 1095 ms 47176 KB Time limit exceeded
10 Execution timed out 1095 ms 41020 KB Time limit exceeded