Submission #306217

---

Source Code Expand

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,sz(v))
#define eb emplace_back
#define mt make_tuple
#define aur auto&
#define bit(n) (1LL<<(n))
using namespace std;
typedef long long ll;
//#define int long long
static const int INF = 1<<25;
static const double EPS = 1e-5;
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}

/*
 * zip.add(hoge), zip.add(all(v)) => 座標の追加
 * zip.compile() => 圧縮実行(しないでも番号付けはする)
 * zip[元の座標] => 圧縮後の座標
 * zip(圧縮後) => 元の座標
 */
template<typename T> struct Zipper{//{{{
    map<T, int> zip;
    vector<T> unzip;
    template<typename It> inline void add(It b, It e){ while(b != e) add(*b++); }
    inline void add(const T &x){//{{{
        if(zip.count(x)) return;
        zip[x] = unzip.size();
        unzip.emplace_back(x);
    }//}}}
    inline void compile(){//{{{
        int i = 0;
        for(auto &x : zip) unzip[x.second = i++] = x.first;
    }//}}}
    inline const int operator[](const T &x){//{{{
        add(x);
        return zip[x];
    }//}}}
    inline const T operator()(const int &i) const { return unzip[i]; }
    inline int size() const { return zip.size(); }
    typename vector<T>::const_iterator begin(){ return unzip.begin(); }
    typename vector<T>::const_iterator end(){ return unzip.end(); }
    T ub1(T x){ return zip.upper_bound(x)->first; }
    T lb1(T x){ return zip.lower_bound(x)->first; }
    T ub2(T x){ return zip.upper_bound(x)->second; }
    T lb2(T x){ return zip.lower_bound(x)->second; }
};//}}}


/*
 * propagate を実装する.
 * 今は範囲外見ないようにしてる.(単位元が無い時用).
 * 範囲外に zero をちゃんと使いたいなら末尾コメントの行を削除.
 *  SegTree(int n, T zero = T())
 *  SegTree(vector<T> xs, T zero = T())
 *  at(int idx), set(int idx, T x), add(int i, T x), sum(int l, int r)
 */
template<typename T>
struct SegTree{//{{{
    const T zero;
    vector<T> tree;
    int offset, N;

    T propagate(const T &l, const T &r){
        return l * r;
    }

    SegTree(int n, const T zero = T()) : zero(zero){
        N = 1;
        while(N < n) N <<= 1;
        tree.assign(N*2, zero);
        offset = N-1;
    }
    SegTree(const vector<T> &xs, const T zero = T()) : zero(zero){
        int n = xs.size();
        N = 1;
        while(N < n) N <<= 1;
        tree.assign(N*2, zero);
        offset = N-1;
        rep(i, n) tree[i + offset] = xs[i];
        build(0, n, 0, 0, N);
    }
    const T &build(const int &l, const int &r, const int &k, const int &ll, const int &rr){
        if(r <= ll || rr <= l) return zero;
        if(rr - ll == 1) return tree[k];
        const int mm = (ll + rr) >> 1;
        if(r <= mm) return tree[k] = build(l, r, k*2+1, ll, mm); ////
        if(l >= mm) return tree[k] = build(l, r, k*2+2, mm, rr); ////
        return tree[k] = propagate(build(l, r, k*2+1, ll, mm), build(l, r, k*2+2, mm, rr));
    }
    T at(int i){ return tree[i + offset]; }
    void set(int i, const T &x){
        i += offset;
        tree[i] = x;
        while(i){
            i = (i-1) >> 1;
            tree[i] = propagate(tree[i*2+1], tree[i*2+2]);
        }
    }
    void add(int i, const T &x){
        i += offset;
        tree[i] = propagate(x, tree[i]);
        while(i){
            i = (i-1) >> 1;
            tree[i] = propagate(tree[i*2+1], tree[i*2+2]);
        }
    }
    T sum(const int &l, const int &r){ return sum(l, r, 0, 0, N); }
    T sum(const int &l, const int &r, const int &k, const int &ll, const int &rr){
        if(r <= ll || rr <= l) return zero;
        if(l <= ll && rr <= r) return tree[k];
        const int mm = (ll + rr) >> 1;
        if(r <= mm) return sum(l, r, k*2+1, ll, mm); ////
        if(l >= mm) return sum(l, r, k*2+2, mm, rr); ////
        return propagate(sum(l, r, k*2+1, ll, mm), sum(l, r, k*2+2, mm, rr));
    }
};//}}}

bool solve(){
    int n; cin >> n;
    vector<int> s(n), t(n);
    rep(i, n) cin >> s[i] >> t[i];
    Zipper<int> zip;
    zip.add(-1); zip.add(1<<30);
    rep(i, n) zip.add(s[i]), zip.add(t[i]);
    zip.compile();
    vector<int> acc(zip.size());
    rep(i, n) acc[zip[s[i]]] += 1;
    rep(i, n) acc[zip[t[i]]] -= 1;
    repsz(i, acc) if(i) acc[i] += acc[i-1];

    SegTree<long double> tree(sz(acc), (long double)1.0);
    rep(i, n) tree.set(zip[t[i]],
            (long double)(acc[zip[t[i]]]) / (acc[zip[t[i]]] + 1));
    rep(i, n){
        long double a = 1.0 - tree.sum(zip[s[i]], zip[t[i]]);
        long double b = acc[zip[t[i]]] / (long double)(acc[zip[t[i]]]+1);
        cout << a << " " << (1-a) * b << endl;
    }
    return true;
}
signed main(){
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);
    cout.setf(ios::fixed); cout.precision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result