結果

問題 No.728 ギブ and テイク
ユーザー mugen_1337mugen_1337
提出日時 2020-09-16 22:05:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 4,280 bytes
コンパイル時間 3,659 ms
コンパイル使用メモリ 213,360 KB
実行使用メモリ 814,744 KB
最終ジャッジ日時 2023-09-04 04:02:10
合計ジャッジ時間 7,238 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
5,004 KB
testcase_13 MLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

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