Submission #453794

#	Time	Username	Problem	Language	Result	Execution time	Memory
453794		RGBB	Vudu (COCI15_vudu)	C++14	140 / 140	540 ms	29448 KiB

vudu

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000000;
int n,lef,rig,mid,bit[MAXN+1];
ll r,input[MAXN],sorted[MAXN];
void update(int pos){
    pos++;
    while(pos<=n){
        bit[pos]++;
        pos+=(pos&(-pos));
    }
}
int query(int pos){
    int sum=0;
    pos++;
    while(pos>0){
        sum+=bit[pos];
        pos-=(pos&(-pos));
    }
    return sum;
}
int bs(ll val){
    lef=0;
    rig=n-1;
    mid=(lef+rig)/2;
    while(rig-lef>1){
        if(sorted[mid]>=val)rig=mid;
        else lef=mid;
        mid=(lef+rig)/2;
    }
    if(sorted[lef]==val)return lef;
    else return rig;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(bit,0,sizeof(bit));
    cin>>n;
    for(int i=0;i<n;i++)cin>>input[i];
    cin>>r;
    for(int i=0;i<n;i++){
        input[i]-=r;
        if(i!=0)input[i]+=input[i-1];
        sorted[i]=input[i];
    }
    sort(sorted,sorted+n);
    ll outp=0;
    for(int i=0;i<n;i++){
        outp+=query(bs(input[i]));
        if(input[i]>=0)outp++;
        update(bs(input[i]));
    }
    cout<<outp;
}

• Subtask 1: 140 / 140