結果

問題 No.728 ギブ and テイク
コンテスト
ユーザー mugen_1337
提出日時 2020-09-16 22:05:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,280 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 210,988 KB
最終ジャッジ日時 2025-01-14 15:21:26
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 MLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
 
struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

template<typename T>
struct BinaryIndexedTree{
    vector<T> data;
    BinaryIndexedTree()=default;
    BinaryIndexedTree(int sz):data(sz+1,0){}
    BinaryIndexedTree(const vector<T> &a):data(a.size()+1,0){
        for(int i=0;i<(int)a.size();i++)data[i+1]=a[i];
        for(int i=1;i<(int)data.size();i++){
            int j=i+(i&-i);
            if(j<(int)data.size()) data[j]+=data[i];
        }
    }
    void add(int k,const T &x){for(++k;k<(int)data.size();k+=(k&-k)) data[k]+=x;}
    // sum [0,k)
    T sum(int k){
        T ret=T();
        for(;k>0;k-=(k&-k))ret+=data[k];
        return ret;
    }
    // sum [l,r)
    T query(int l,int r){
        return sum(r)-sum(l);
    }
    T operator[](const int &k){return query(k,k+1);}
    // sum[0,i)>=xとなる最小のi
    int lower_bound(T x){
        int r=1,i=0;
        while(r<(int)data.size())r<<=1;
        for(;r>0;r>>=1)if(i+r<(int)data.size() and data[i+r]<x){
            x-=data[i+r];i+=r;
        }
        return i+1;
    }
};

// x, yの値を先読みできればオンラインにできる．
template<typename Tx,typename Ty>
struct RangeTree{
    vector<Tx> xs;
    vector<Ty> ys;
    int sz,ysz;
    vector<BinaryIndexedTree<int>> seg;
    RangeTree(vector<Tx> xs_,vector<Ty> ys_):xs(xs_),ys(ys_){
        sort(begin(xs),end(xs));
        xs.erase(unique(begin(xs),end(xs)),end(xs));
        sort(begin(ys),end(ys));
        ys.erase(unique(begin(ys),end(ys)),end(ys));

        sz=1;ysz=(int)ys.size();
        while(sz<(int)xs.size()) sz<<=1;
        seg.assign(2*sz,BinaryIndexedTree<int>(ysz));
    }
    // 先読みさせてない値を入れない
    void add(Tx x,Ty y){
        int k=lower_bound(begin(xs),end(xs),x)-begin(xs);
        int yi=lower_bound(begin(ys),end(ys),y)-begin(ys);
        k+=sz;
        for(;k;k>>=1) seg[k].add(yi,1);
    }
    void erase(Tx x,Ty y){
        int k=lower_bound(begin(xs),end(xs),x)-begin(xs);
        int yi=lower_bound(begin(ys),end(ys),y)-begin(ys);
        k+=sz;
        for(;k;k>>=1) seg[k].add(yi,-1);
    }
    // これは先読みしていなくてもかまわない
    int count(Tx xl,Tx xr,Ty yl,Ty yh){
        int l=lower_bound(begin(xs),end(xs),xl)-begin(xs);
        int r=lower_bound(begin(xs),end(xs),xr)-begin(xs);
        int lw=lower_bound(begin(ys),end(ys),yl)-begin(ys);
        int hi=lower_bound(begin(ys),end(ys),yh)-begin(ys);
        l+=sz,r+=sz;
        int ret=0;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                ret+=seg[l].query(lw,hi);
                l++;
            }
            if(r&1){
                r--;
                ret+=seg[r].query(lw,hi);
            }
        }
        return ret;
    }
};

void solve(){
    int n;cin>>n;
    vector<ll> a(n),l(n),r(n),b(n);
    cin>>a;
    rep(i,n) cin>>l[i]>>r[i];
    rep(i,n) b[i]=a[i]+r[i];
    RangeTree<ll,ll> seg(a,b);
    
    ll res=0;
    rep(i,n){
        res+=seg.count(a[i]-l[i],LINF,a[i],LINF);
        seg.add(a[i],a[i]+r[i]);
    }
    cout<<res<<endl;
}


signed main(){
    solve();
    return 0;
}
0