Submission #306497

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,n) for(__typeof((n).begin()) it=(n).begin();it!=(n).end();++it)

using namespace std;

typedef long long ll;

const double eps = 1e-8;

class SegmentTree
{
public:
    typedef double Int;
    const Int DEFAULT_VALUE = 1; 
    vector<Int> data;
    Int N;
    
    inline Int func(Int x, Int y) {
        return x * y;
    }
    
    inline void updateLeaf(Int v, Int val) {
        data[v] = val;
    }
    
    SegmentTree(Int n) {
        vector<Int> vec(n, DEFAULT_VALUE);
        construct(n);
    }
    
    SegmentTree(vector<Int> vec) {
        construct(vec.size());
        for (int i = 0; i < (Int)vec.size(); i++) {
            update(i, vec[i]);
        }
    }
    
    void construct(int n) {
        int x = 1;
        while (x < n) {
            x *= 2;
        }
        
        this->N = x;
        data = vector<Int>(2 * x, DEFAULT_VALUE);
    }
    
    Int get(int l, int r) {
        return getSub(l, r, 0, N, 1);
    }
    
    void update(Int index, Int val) {
        int v = index + N;
        updateLeaf(v, val);
        
        v /= 2;
        while (v > 0) {
            data[v] = func(data[2 * v], data[2 * v + 1]);
            if (data[v] < eps) data[v] = 0;
            v /= 2;
        }
    }
    
    Int getSub(int l, int r, int myl, int myr, Int v) {
        if (myr <= l || r <= myl) return DEFAULT_VALUE;
        if (l <= myl && myr <= r) return data[v];
        
        int mid = (myl + myr) / 2;
        return func(getSub(l, r, myl, mid, 2 * v),
                    getSub(l, r, mid, myr, 2 * v + 1));
    }
};


int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> s(N), t(N);
    map<int, int> time;
    rep(i, N) {
        cin >> s[i] >> t[i];
        time[s[i]] = 0, time[t[i]] = 0;
    }

    int it = 0;
    for (auto &x: time) {
        x.second = it++;
    }

    priority_queue<pair<int, bool> > q;
    rep(i, N) {
        q.push({-time[s[i]], true});
        q.push({-time[t[i]], false});
    }

    int count = 0;
    SegmentTree seg(it);

    while (!q.empty()) {
        auto e = q.top();
        int t = -e.first;
        q.pop();
        if (e.second) {
            count++;
            seg.update(t, 1.0);
        } else {
            seg.update(t,(double)(count - 1) / (double)count);
            count--;
        }
    }

    cout << setprecision(10);
    rep(i, N) {
        cout << 1.0 - seg.get(time[s[i]], time[t[i]]) << " ";
        cout << seg.get(time[s[i]], time[t[i]] + 1) << endl;
    }

    return 0;
}

Submission Info

Judge Result