結果
問題 | No.2462 七人カノン |
ユーザー |
![]() |
提出日時 | 2023-09-08 21:45:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 3,037 bytes |
コンパイル時間 | 2,145 ms |
コンパイル使用メモリ | 206,384 KB |
最終ジャッジ日時 | 2025-02-16 19:45:06 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
// (◕ᴗ◕✿) #include <bits/stdc++.h> #define rep(i, n) for (ll i = 0; i < (n); i++) #define srep(i, s, n) for (ll i = s; i < (n); i++) #define len(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>; using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>; using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>; using uint = unsigned int; using ull = unsigned long long; const ld pi = 3.141592653589793; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; // const ll mod = 1000000007; const ll mod = 998244353; inline bool inside(long long y, long long x, long long H, long long W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); } #define debug(var) do{std::cout << #var << " : \n";view(var);}while(0) template<typename T> void view(T e){cout << e << endl;} template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;} template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } } int op1(int a, int b){return a + b;}; int e1(){return 0;}; ld op2(ld a, ld b){return a + b;}; ld e2(){return 0;}; template<class T, T (*op)(T, T), T (*e)()> struct segtree{ public : segtree(int n) : _n(n){ depth = 0; while ((1 << depth) < _n) depth++; size = 1 << depth; tree = vc<T>(2 * size, e()); } void set(int p, T x){ assert (0 <= p && p < _n); p += size; tree[p] = x; for (int i = 0; i < depth; i++){ p >>= 1; tree[p] = op(tree[2 * p], tree[2 * p + 1]); } return; } T get(int p){ assert(0 <= p && p < _n); return tree[p + size]; } T prod(int l, int r){ assert (0 <= l && l < r && r <= _n); T nl = e(), nr = e(); l += size; r += size; while(l < r){ if (l & 1) nl = op(nl, tree[l++]); if (r & 1) nr = op(nr, tree[--r]); l >>= 1; r >>= 1; } return op(nl, nr); } private : int _n, depth, size; vc<T> tree; }; int main(){ int N, Q; cin >> N >> Q; vv<pair<int, int>> query(N); segtree<int, op1, e1> seg1(100100); rep(i, Q){ int id, s, t; cin >> id >> s >> t; id--; query[id].push_back({s, t}); seg1.set(s, seg1.get(s) + 1); seg1.set(t, seg1.get(t) - 1); } segtree<ld, op2, e2> seg2(100100); rep(i, 100010) seg2.set(i, (ld)1 / (ld)seg1.prod(0, i + 1)); vld ret(N); rep(i, N) for (auto [s, t] : query[i]) ret[i] += seg2.prod(s, t); for (auto x : ret) cout << fixed << setprecision(16) << x << endl; }