제출 #621070

#제출 시각아이디문제언어결과실행 시간메모리
621070sword060Vudu (COCI15_vudu)C++17
42 / 140
280 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6+5; long long seg[4*N],xd,ans,a[N],x,k; vector<long long>comp; map<long long,int>mp; long long query(int i,int l,int r,int s,int e){ if(l>e||r<s)return 0; if(l>=s&&r<=e){ return seg[i]; } int mid=(l+r)/2; return (query((i<<1),l,mid,s,e)+query((i<<1|1),mid+1,r,s,e)); } void update(int i,int l,int r,int s){ if(l>s||r<s)return; if(l==s&&r==s){ seg[i]++; return; } int mid = (l+r)/2; update((i<<1),l,mid,s); update((i<<1|1),mid+1,r,s); seg[i]=(seg[i<<1]+seg[i<<1|1]); } int main(){ ios::sync_with_stdio(0);cin.tie(0); for(int i=0;i<4*N;i++)seg[i]=0; cin>>x; for(int i=0;i<x;i++)cin>>a[i]; cin>>k; comp.push_back(0); for(int i=0;i<x;i++){ a[i]-=k; xd+=a[i]; comp.push_back(xd); } sort(comp.begin(),comp.end()); int z=0; for(int i=(int)comp.size()-1;i>=0;i--)if(mp.find(comp[i])==mp.end())mp[comp[i]]=z++; xd=0; update(1,0,N,mp[0]); for(int i=0;i<x;i++){ xd+=a[i]; ans+=query(1,0,N,mp[xd],N); update(1,0,N,mp[xd]); } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...