oj.uz

Submission #555352

# Submission time Handle Problem Language Result Execution time Memory
555352 2022-04-30T15:05:11 Z new_acc Vudu (COCI15_vudu) C++14
140 / 140
 288 ms 41308 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 281 ms 39960 KB Output is correct
5 Correct 149 ms 22680 KB Output is correct
6 Correct 232 ms 35352 KB Output is correct
7 Correct 241 ms 36800 KB Output is correct
8 Correct 210 ms 31992 KB Output is correct
9 Correct 288 ms 41308 KB Output is correct
10 Correct 241 ms 35836 KB Output is correct