結果
| 問題 |
No.2462 七人カノン
|
| コンテスト | |
| ユーザー |
 ococonomy1
|
| 提出日時 | 2023-09-08 21:40:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 354 ms / 2,000 ms |
| コード長 | 6,911 bytes |
| コンパイル時間 | 1,269 ms |
| コンパイル使用メモリ | 121,088 KB |
| 最終ジャッジ日時 | 2025-02-16 19:41:56 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using lg = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<lg, lg>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
// #define AMARI 1000000007
#define TEMOTO ((sizeof(long double) == 16) ? false : true)
#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)
#define el '\n'
#define El '\n'
// 抽象再帰セグ木？（抽象セグ木の定義分からんな）（遅延ではない）
// ococo_segtree<int> rsq(n,0);みたいに宣言する
template <typename T> class ococo_segtree {
T func(T a, T b) {
// ここに演算を入れる
return (a + b);
}
public:
int n;
T tmax;
// range minimum query
vector<T> rmq;
//(データの大きさ,単位元)
ococo_segtree(int N, T t) {
syokica(N, t);
}
// 配列の初期化 O(N)
void syokica(int a, T t) {
n = 1;
tmax = t;
while(n < a) n *= 2;
rmq.resize(2 * n - 1);
for(int i = 0; i < 2 * n - 1; i++) {
rmq[i] = tmax;
}
}
// a[i]をxにする O(logN)
void update_num(int i, T x) {
i += (n - 1);
rmq[i] = x;
while(i) {
i = (i - 1) / 2;
rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]);
}
}
// a[i]にxを加える O(logN)
void add_num(int i, T x) {
i += (n - 1);
rmq[i] = func(rmq[i], x);
while(i) {
i = (i - 1) / 2;
rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]);
}
}
T get_minimum2(int a, int b, int k, int l, int r) {
if(a <= l && r <= b) return rmq[k];
else if(r <= a || b <= l) return tmax;
else
return func(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2),
get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r));
}
//[l,r)の区間演算の取得 O(logN)
T get_val(int l, int r) {
return get_minimum2(l, r, 0, 0, n);
}
};
// 区間可算ができる遅延セグ木
// 最小値の取得と、区間和の取得ができる
template <typename T> class ococo_raq_lazy_segtree {
public:
int n;
T tmax;
// rsq:Range Sum Query
vector<T> rsq, lazy_rsq;
// rmq;Range Minimum Query
vector<T> rmq, lazy_rmq;
ococo_raq_lazy_segtree(int N, T t) {
syokica(N, t);
}
// 配列の初期化 O(N)
//(サイズ、指定した型の最大値)を引数にとる
// rmqをtmax（指定した型の最大値）で初期化しているが、場合に合わせて初期化する値は変えた方が良いこともある。
void syokica(int a, T t) {
n = 1;
tmax = t;
while(n < a) n *= 2;
rsq.resize(2 * n - 1);
rmq.resize(2 * n - 1);
lazy_rsq.resize(2 * n - 1);
lazy_rmq.resize(2 * n - 1);
for(int i = 0; i < 2 * n - 1; i++) {
rsq[i] = 0;
rmq[i] = tmax;
lazy_rsq[i] = 0;
lazy_rmq[i] = tmax;
}
}
// k番目の点についての遅延評価 O(1)
void lazy_evaluate(int k, int l, int r) {
if(lazy_rsq[k] != 0) {
rsq[k] += lazy_rsq[k];
if(r - l > 1) {
lazy_rsq[2 * k + 1] += (lazy_rsq[k] / 2);
lazy_rsq[2 * k + 2] += (lazy_rsq[k] / 2);
}
lazy_rsq[k] = 0;
}
if(lazy_rmq[k] != tmax) {
rmq[k] += lazy_rmq[k];
if(r - l > 1) {
if(lazy_rmq[2 * k + 1] == tmax)
lazy_rmq[2 * k + 1] = lazy_rmq[k];
else lazy_rmq[2 * k + 1] += lazy_rmq[k];
if(lazy_rmq[2 * k + 2] == tmax)
lazy_rmq[2 * k + 2] = lazy_rmq[k];
else lazy_rmq[2 * k + 2] += lazy_rmq[k];
}
lazy_rmq[k] = tmax;
}
}
void add_num2(int a, int b, T x, int k, int l, int r) {
lazy_evaluate(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
lazy_rsq[k] += (T)(r - l) * x;
if(lazy_rmq[k] == tmax) lazy_rmq[k] = x;
else lazy_rmq[k] += x;
lazy_evaluate(k, l, r);
} else {
add_num2(a, b, x, 2 * k + 1, l, (l + r) / 2);
add_num2(a, b, x, 2 * k + 2, (l + r) / 2, r);
rsq[k] = rsq[2 * k + 1] + rsq[2 * k + 2];
rmq[k] = min(rmq[2 * k + 1], rmq[2 * k + 2]);
}
}
//[l,r)にxを加える
void add_num(int l, int r, T x) {
add_num2(l, r, x, 0, 0, n);
}
T get_sum2(int a, int b, int k, int l, int r) {
if(r <= a || b <= l) return 0;
lazy_evaluate(k, l, r);
if(a <= l && r <= b) return rsq[k];
else {
return (get_sum2(a, b, k * 2 + 1, l, (l + r) / 2) +
get_sum2(a, b, k * 2 + 2, (l + r) / 2, r));
}
}
//[l,r)の和の取得 O(logN)
T get_sum(int l, int r) {
return get_sum2(l, r, 0, 0, n);
}
T get_minimum2(int a, int b, int k, int l, int r) {
if(r <= a || b <= l) return tmax;
lazy_evaluate(k, l, r);
if(a <= l && r <= b) return rmq[k];
else
return min(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2),
get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r));
}
//[l,r)の最小値の取得 O(logN)
T get_minimum(int l, int r) {
return get_minimum2(l, r, 0, 0, n);
}
};
#define MULTI_TEST_CASE false
void solve(void) {
int n,q;
cin >> n >> q;
vector<vector<pii>> ensou(n);
ococo_raq_lazy_segtree<int> ilos(1e5+1,0);
while(q--){
int i,s,t;
cin >> i >> s >> t;
i--;
ensou[i].push_back(pair(s,t));
ilos.add_num(s,t,1);
//cerr << s << t << el;
//cerr << ilos.get_sum(s,s + 1) << el;
}
ococo_segtree<long double> dos(1e5+1,0);
for(int i = 0; i < 1e5; i++){
dos.add_num(i,1 / (ld)ilos.get_sum(i,i+1));
//if(i == 0)cerr << ilos.get_minimum(0,1);
}
vector<ld> ans(n);
cout << fixed << setprecision(15);
for(int i = 0; i < n; i++){
for(int j = 0; j < ensou[i].size(); j++){
ans[i] += dos.get_val(ensou[i][j].first,ensou[i][j].second);
}
cout << ans[i] << el;
}
return;
}
void calc(void) {
return;
}
int main(void) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
calc();
int t = 1;
if(MULTI_TEST_CASE) cin >> t;
while(t--) {
solve();
}
return 0;
}