# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
622919 | 3omar_ahmed | Vudu (COCI15_vudu) | C++17 | 231 ms | 57036 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 0 ;
if (s <= l && r <= e && val >= seg[i]) return r - l + 1 ;
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 = 1 ; 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |