제출 #622954

#제출 시각아이디문제언어결과실행 시간메모리
6229543omar_ahmedVudu (COCI15_vudu)C++17
42 / 140
1101 ms65536 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...