Submission #555352

#	Time	Username	Problem	Language	Result	Execution time	Memory
555352		new_acc	Vudu (COCI15_vudu)	C++14	140 / 140	288 ms	41308 KiB

vudu

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<20;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+1],val[N];
pair<ll,int> sp[N];
void upd(int a,int ind){
    for(ind+=SS;ind>0;ind>>=1) seg[ind]+=a;
}
int Query(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) res+=seg[a+1];
        if(b&1) res+=seg[b-1];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;    
    for(int i=1;i<=n;i++) cin>>t[i];
    int p;
    cin>>p;
    for(int i=1;i<=n;i++) t[i]-=p;
    for(int i=1;i<=n;i++) sp[i].se=i,sp[i].fi=sp[i-1].fi+(ll)t[i];
    sort(sp,sp+1+n);
    int curr=0;
    for(int i=0;i<=n;i++){
        if(i==0 or sp[i].fi!=sp[i-1].fi) curr++;
        val[sp[i].se]=curr;
    }
    upd(1,val[0]);
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=(ll)Query(1,val[i]);
        upd(1,val[i]);
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

• Subtask 1: 140 / 140