Submission #949728

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(ll i = (ll)(k); i < (ll)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pdd;
const ll MOD = 1000000007;
const ll INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

struct Data
{
	pdd num;
	Data() :num(1, 0) {};
	Data(pdd n) { num = n; };
};

struct SegmentTree
{
	ll n; vector<Data> data;
	SegmentTree(ll N)
	{
		n = 1;
		while (n < N) n *= 2;
		data.resize(2 * n);
	}
private:
	Data sub(ll left, ll right, ll node, ll nleft, ll nright)
	{
		if (nright <= left || right <= nleft) return Data();
		if (left <= nleft && nright <= right) return data[node];
		Data vl = sub(left, right, node * 2 + 1, nleft, (nleft + nright) / 2);
		Data vr = sub(left, right, node * 2 + 2, (nleft + nright) / 2, nright);
		return pdd(vl.num.first * vr.num.first, vl.num.second * vr.num.first + vr.num.second);
	}

public:
	void update(ll pos, Data value)
	{
		pos += n - 1;
		data[pos] = value;
		while (pos > 0)
		{
			pos = (pos - 1) / 2;
			ld a = data[pos * 2 + 1].num.first, b = data[pos * 2 + 1].num.second;
			ld c = data[pos * 2 + 2].num.first, d = data[pos * 2 + 2].num.second;
			data[pos] = pdd(a * c, b * c + d);
		}
	}
	ld get()
	{
		return data[0].num.first + data[0].num.second;
	}
};

typedef pair<ll, pdd> query;

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	ll n, m;
	cin >> n >> m;
	vector<query> q;
	set<ld> st;

	REP(i, m)
	{
		ll a; ld b, c;
		cin >> a >> b >> c;
		a--;
		st.insert(a);
		q.emplace_back(a, pdd(b, c));
	}

	map<ld, ll> dict;
	ll sz = 0;
	for (auto i : st) dict[i] = sz++;

	SegmentTree seg(sz);
	ld ansmax = 1, ansmin = 1;
	REP(i, m)
	{
		ll id = dict[q[i].first];
		pdd a = q[i].second;
		seg.update(id, a);
		ld tmp = seg.get();
		chmax(ansmax, tmp);
		chmin(ansmin, tmp);
	}
	cout << ansmin << endl;
	cout << ansmax << endl;
	return 0;
}

Submission Info

Judge Result