Submission #1625584

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,bg,ed) for(int i=bg;i<ed;i++)
#define REP(i,n) FOR(i,0,n)
typedef long long LL;
template <typename T>
istream& operator>>(istream& is,vector<T> &v){
  for(auto &it:v)
    is>>it;
  return is;
}

template <typename T>
bool chmax(T &l,T r){
    bool f=(l<r);
    if(f)l=r;
    return f;
}
typedef vector<int> V;
typedef vector<V> VV;
#define pb push_back

namespace BIT_{
    LL t[512345];
    inline LL* get(){
        return t;
    }
}

struct BIT{
    using T=LL;
    T* bit;
    int n;
    BIT(T* tb,int n):bit(tb),n(n){
        REP(i,n+1)bit[i]=0;
    }
    BIT(int n):BIT(BIT_::get(),n){}
    void add(int i,T x){
        while(i<=n){
            bit[i]+=x;
            //cout<<"add:"<<i<<" "<<bit[i]<<endl;
            i+=i&-i;

        }
    }
    LL sum(int i){
        //cout<<"q:"<<i<<endl;;
        LL s=0;
        while(i>0){
            s+=bit[i];
            //cout<<i<<" "<<bit[i]<<endl;;
            i-=i&-i;
        }
        return s;
    }
    LL sum(int lb,int ub){
        if(ub<lb)return 0;
        return sum(ub)-sum(lb-1);
    }

};

int N;
LL C;

pair<int,LL> bw[112345];
#define fi first
#define se second
BIT bit(112345);
LL f(const int l,const int r){
    LL ret=0;
    if(r-l<=3){
        FOR(i,l,r)
            FOR(j,i+1,r){
            if(bw[i].fi>bw[j].fi){
                LL x=min(bw[i].se,bw[j].se);
                LL y=max(bw[i].se,bw[j].se);
                ret+=C*x+y;
            }
        }
    }
    else{
        const int m=(l+r)/2;
        ret+=f(l,m);
        ret+=f(m,r);
        //FOR(i,l,r)cout<<"("<<bw[i].fi<<","<<bw[i].se<<")"<<endl;
        {
            int rr=m;
            FOR(ll,l,m){
                while(rr<r&&bw[ll].fi>bw[rr].fi){
                    bit.add(bw[rr].second,bw[rr].second);
                    //cout<<"add:"<<bw[rr].second<<endl;
                    rr++;
                }
                ret+=bit.sum(bw[ll].se,100010);

                ret+=C*bit.sum(bw[ll].se-1);
                //cout<<"sum:"<<bw[ll].se<<" "<<bit.sum(bw[ll].se+1,100010)<<endl;
            }
            FOR(i,m,rr)bit.add(bw[i].second,-bw[i].second);
        }

        {
            int ll=m-1;
            for(int rr=r-1;rr>=m;rr--){
                while(ll>=l&&bw[rr].fi<bw[ll].fi){
                    bit.add(bw[ll].second,bw[ll].second);
                    ll--;
                }
                ret+=bit.sum(bw[rr].se+1,100010);
                ret+=C*bit.sum(bw[rr].se);
            }
            for(int i=m-1;i>ll;i--)bit.add(bw[i].second,-bw[i].second);
        }

    }
    sort(bw+l,bw+r);
    return ret;
}

int main(){

    cin>>N>>C;
    REP(i,N){
        cin>>bw[i].first>>bw[i].second;
    }
    cout<<f(0,N)<<endl;
    
}

Submission Info

Judge Result