#include 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<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const pair&p){ os< ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,pair&p){ is>>p.first>>p.second; return is; } template istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } #include #include using namespace __gnu_pbds; // x軸だけ先に読めれば, オンラインにできる. 僕にはこれが限界 template struct RangeTree{ // pair value, id using set_pbds=tree,null_type,less>,rb_tree_tag,tree_order_statistics_node_update>; map cnt; vector seg; vector xs; int sz; RangeTree(vector x_):xs(x_){ sort(begin(xs),end(xs)); xs.erase(unique(begin(xs),end(xs)),end(xs)); sz=1; while(sz<(int)xs.size()) sz<<=1; while((int)xs.size()::max()); seg.assign(2*sz,set_pbds()); } void add(Tx x,Ty y){ int k=lower_bound(begin(xs),end(xs),x)-begin(xs); assert(xs[k]==x); k+=sz; int id=cnt[y]++; for(;k;k>>=1) seg[k].insert({y,id}); } void erase(Tx x,Ty y){ int k=lower_bound(begin(xs),end(xs))-begin(xs); k+=sz; int id=--cnt[y]; for(;k;k>>=1) seg[k].erase({y,id}); } // [xleft, xright), [ylow, yhigh) 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); l+=sz,r+=sz; int ret=0; for(;l>=1,r>>=1){ if(l&1){ ret+=seg[l].order_of_key({yh,-1})-seg[l].order_of_key({yl,-1}); l++; } if(r&1){ r--; ret+=seg[r].order_of_key({yh,-1})-seg[r].order_of_key({yl,-1}); } } return ret; } }; /* 数え上げるものの条件は i= A_j-L_j A_i+R_i >= A_j 後ろから点を追加しながら左下を数える */ void solve(){ int n;cin>>n; vector a(n),l(n),r(n); cin>>a; rep(i,n) cin>>l[i]>>r[i]; RangeTree seg(a); 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<