結果

問題 No.728 ギブ and テイク
ユーザー mugen_1337mugen_1337
提出日時 2020-09-15 01:51:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,409 bytes
コンパイル時間 3,770 ms
コンパイル使用メモリ 249,744 KB
実行使用メモリ 461,464 KB
最終ジャッジ日時 2023-09-04 00:56:51
合計ジャッジ時間 14,508 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,756 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 133 ms
28,360 KB
testcase_14 AC 248 ms
41,128 KB
testcase_15 AC 90 ms
19,164 KB
testcase_16 AC 216 ms
37,608 KB
testcase_17 AC 191 ms
35,116 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
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;
}

#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