結果

問題 No.2462 七人カノン
ユーザー ococonomy1ococonomy1
提出日時 2023-09-08 21:40:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 6,911 bytes
コンパイル時間 1,447 ms
コンパイル使用メモリ 123,520 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2024-06-26 14:33:52
合計ジャッジ時間 12,333 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 289 ms
11,520 KB
testcase_01 AC 222 ms
11,520 KB
testcase_02 AC 288 ms
11,676 KB
testcase_03 AC 66 ms
11,876 KB
testcase_04 AC 65 ms
11,904 KB
testcase_05 AC 65 ms
11,776 KB
testcase_06 AC 66 ms
11,900 KB
testcase_07 AC 66 ms
11,860 KB
testcase_08 AC 65 ms
11,648 KB
testcase_09 AC 66 ms
11,808 KB
testcase_10 AC 65 ms
11,696 KB
testcase_11 AC 64 ms
11,664 KB
testcase_12 AC 65 ms
11,796 KB
testcase_13 AC 290 ms
16,640 KB
testcase_14 AC 289 ms
17,408 KB
testcase_15 AC 285 ms
16,868 KB
testcase_16 AC 313 ms
17,596 KB
testcase_17 AC 327 ms
17,756 KB
testcase_18 AC 80 ms
15,480 KB
testcase_19 AC 77 ms
15,616 KB
testcase_20 AC 239 ms
18,680 KB
testcase_21 AC 236 ms
18,520 KB
testcase_22 AC 248 ms
18,688 KB
testcase_23 AC 238 ms
18,560 KB
testcase_24 AC 201 ms
17,152 KB
testcase_25 AC 332 ms
18,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #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;
}
0