2012-2013 neercshool 17 november Taks C

/*

for every current segment , I find all segments , that have common points with current.
After that I joined these segments to current segment. To find fast maximum color I used Set.

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
#define f0(a) memset(a, 0, sizeof(a))
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define vi vector<int>
#define ll long long

#ifdef WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif
const int maxn = (int)1e6;
struct Tree {
    int Max, flag ;
    Tree() {
        Max = 0, flag = -1;
    }
} T[maxn * 4];

struct CMPAVE {
    bool operator() (const pair<ll, int> a, pair<ll, int> b) const {
        double x = a.f * 1.0 / a.s;
        double y = b.f * 1.0 / b.s;
        return y - x > 1e-5;
    }
};

pair<pii, int > e[maxn];
int A[maxn], An;
pair<ll, int> COL[maxn];
int le[maxn], ri[maxn];
multiset<pair<ll, int> , CMPAVE> AVE;
int p[maxn], rank[maxn];
int n;

void Push(int v, int sl, int sr) {

    if (T[v].flag == -1) return;

    T[v].Max = T[v].flag;
    if (sl != sr)
        T[v + v].flag = T[v + v + 1].flag = T[v].flag;

    T[v].flag = -1;
}

int findMax(int v, int sl, int sr, int l, int r) {
    Push(v, sl, sr);

    if (min(r, sr) - max(l, sl) < 0) return 0;

    if (l <= sl && sr <= r) return T[v].Max;
    int mid = (sl + sr) >> 1;
    return max(findMax(v + v, sl, mid, l, r), findMax(v + v + 1, mid + 1, sr, l, r));
}

void Paint(int v, int sl, int sr, int l, int r, int col) {
    Push(v, sl, sr);

    if (min(sr, r) - max(sl, l) < 0) return;

    if (l <= sl && sr <= r) {
        T[v].flag = col;
        Push(v, sl, sr);
        return;
    }
    int mid = (sl + sr) >> 1;
    Paint(v + v, sl, mid, l, r, col);
    Paint(v + v + 1, mid + 1, sr, l, r, col);
    T[v].Max = max(T[v + v].Max, T[v + v + 1].Max);
}

void join(int u, int v) {
    int lu = le[u], ru = ri[u];
    int &lv = le[v], &rv = ri[v];

    AVE.erase(AVE.find(COL[u]));
    AVE.erase(AVE.find(COL[v]));

    pair<ll, int> tmp = mp(COL[u].f + COL[v].f, COL[u].s + COL[v].s);
    Paint(1, 1, An, lu, ru, 0);
    COL[v] = tmp;
    AVE.insert(tmp);
    lv = min(lv, lu);
    rv = max(rv, ru);
}

int main() {
    freopen("painting.in","r",stdin);
    freopen("painting.out","w",stdout);

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int l, r, col;
        scanf("%d%d%d", &l, &r, &col); --r;
        e[i + 1] = mp(mp(l, r), col);
        A[An++] = l;
        A[An++] = r;
    }

    sort(A, A + An);
    An = unique(A, A + An) - A;

    for (int i = 1; i <= n; ++i) {
        int l = lower_bound(A, A + An, e[i].f.f) - A + 1;
        int r = lower_bound(A, A + An, e[i].f.s) - A + 1;

        le[i] = l; ri[i] = r;
        COL[i] = mp(e[i].s, 1);
        AVE.insert(COL[i]);
        while (true) {
            int with = findMax(1, 1, An, l, r);
            if (with == 0) break;
            join(with, i);
        }

//      cerr << A[le[i] - 1] << " " << A[ri[i] - 1] + 1 << endl;

        Paint(1, 1, An, le[i], ri[i], i);
        set<pair<ll,int> > :: iterator it = AVE.end();
        --it;

        printf("%.6lf\n", it -> f * 1.0 / it -> s);
    }


    return 0;
}