Submission #1156635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156635		spycoderyt	Vudu (COCI15_vudu)	C++20	140 / 140	428 ms	62520 KiB

vudu

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 1e6+5;
int fen[N];
void add(int pos,int val) {
    for(int i = pos;i<N;i+=i&-i)fen[i]+=val;
}
int sum(int pos){
    int res=0;
    for(int i = pos;i>0;i-=i&-i)res+=fen[i];
    return res;
}
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,p;
    ll ans=0;
    cin >> n;
    vector<ll> v(n+1);
    for(int i = 1;i<=n;i++)cin>>v[i];
    cin>>p;
    for(int i = 1;i<=n;i++)v[i] -= p,v[i]+=v[i-1];
    unordered_map<ll,int> mp;
    int cnt = 1;
    vector<ll> tmp = v;
    tmp.push_back(0);
    sort(tmp.begin(),tmp.end());
    for(auto e : tmp) mp[e]=cnt++;

    add(mp[0],1);
    for(int i = 1;i<=n;i++) {
        // cur - pref  >= 0 so pref <= cur
        ans+=sum(mp[v[i]]);
        add(mp[v[i]],1);
        // if(v[i]>=0)ans++;
        // cerr<<ans<<"\n";
    }
    cout << ans;
}

• Subtask 1: 140 / 140