結果

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

ソースコード

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;
}

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// x軸だけ先に読めれば, オンラインにできる. 僕にはこれが限界
template<typename Tx,typename Ty>
struct RangeTree{
    // pair value, id
    using set_pbds=tree<pair<Ty,int>,null_type,less<pair<Ty,int>>,rb_tree_tag,tree_order_statistics_node_update>;
    map<Ty,int> cnt;

    vector<set_pbds> seg;
    vector<Tx> xs;
    int sz;
    RangeTree(vector<Tx> 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()<sz) xs.push_back(numeric_limits<Tx>::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<r;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<j
    A_i >= A_j-L_j
    A_i+R_i >= A_j
    後ろから点を追加しながら左下を数える
*/

void solve(){
    int n;cin>>n;
    vector<ll> a(n),l(n),r(n);
    cin>>a;
    rep(i,n) cin>>l[i]>>r[i];

    RangeTree<ll,ll> 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<<res<<endl;
}

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