oj.uz

Submission #453794

# Submission time Handle Problem Language Result Execution time Memory
453794 2021-08-04T21:44:27 Z RGBB Vudu (COCI15_vudu) C++14
140 / 140
 540 ms 29448 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4300 KB Output is correct
2 Correct 5 ms 4248 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 540 ms 28684 KB Output is correct
5 Correct 271 ms 17988 KB Output is correct
6 Correct 448 ms 25920 KB Output is correct
7 Correct 444 ms 26780 KB Output is correct
8 Correct 411 ms 23768 KB Output is correct
9 Correct 515 ms 29448 KB Output is correct
10 Correct 441 ms 26308 KB Output is correct