oj.uz

Submission #720675

# Submission time Handle Problem Language Result Execution time Memory
720675 2023-04-08T23:30:40 Z Yell0 Vudu (COCI15_vudu) C++17
140 / 140
 303 ms 33556 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MN=1e6+2;
int N,P;
ll pfs[MN],cc[MN],bit[MN],ans=0;

ll qry(int idx) {
    ll out=0;
    for(int i=idx;i>0;i-=i&-i) out+=bit[i];
    return out;
}

void inc(int idx) {
    for(int i=idx;i<=MN;i+=i&-i) bit[i]++;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>pfs[i];
    cin>>P;
    for(int i=1;i<=N;i++) {
        pfs[i]+=pfs[i-1]-P;
        cc[i]=pfs[i];
    }
    sort(cc,cc+1+N);
    for(int i=0;i<=N;i++) {
        int r=lower_bound(cc,cc+1+N,pfs[i])-cc+1;
        ans+=qry(r);
        inc(r);
    }
    cout<<ans<<'\n';
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 303 ms 32584 KB Output is correct
5 Correct 151 ms 18372 KB Output is correct
6 Correct 269 ms 28668 KB Output is correct
7 Correct 240 ms 29832 KB Output is correct
8 Correct 233 ms 26032 KB Output is correct
9 Correct 296 ms 33556 KB Output is correct
10 Correct 251 ms 29104 KB Output is correct