結果
問題 | No.2462 七人カノン |
ユーザー | syndro_6 |
提出日時 | 2023-09-08 21:45:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 336 ms / 2,000 ms |
コード長 | 3,037 bytes |
コンパイル時間 | 2,409 ms |
コンパイル使用メモリ | 208,568 KB |
実行使用メモリ | 15,328 KB |
最終ジャッジ日時 | 2023-09-08 21:45:25 |
合計ジャッジ時間 | 15,443 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 265 ms
8,184 KB |
testcase_01 | AC | 203 ms
8,256 KB |
testcase_02 | AC | 265 ms
8,148 KB |
testcase_03 | AC | 54 ms
8,188 KB |
testcase_04 | AC | 55 ms
8,144 KB |
testcase_05 | AC | 54 ms
8,152 KB |
testcase_06 | AC | 54 ms
8,244 KB |
testcase_07 | AC | 53 ms
8,200 KB |
testcase_08 | AC | 53 ms
8,188 KB |
testcase_09 | AC | 52 ms
8,272 KB |
testcase_10 | AC | 53 ms
8,280 KB |
testcase_11 | AC | 54 ms
8,184 KB |
testcase_12 | AC | 53 ms
8,340 KB |
testcase_13 | AC | 296 ms
13,240 KB |
testcase_14 | AC | 319 ms
14,000 KB |
testcase_15 | AC | 285 ms
13,260 KB |
testcase_16 | AC | 336 ms
14,408 KB |
testcase_17 | AC | 332 ms
14,468 KB |
testcase_18 | AC | 201 ms
11,896 KB |
testcase_19 | AC | 205 ms
11,968 KB |
testcase_20 | AC | 306 ms
15,060 KB |
testcase_21 | AC | 311 ms
15,060 KB |
testcase_22 | AC | 313 ms
15,060 KB |
testcase_23 | AC | 307 ms
15,072 KB |
testcase_24 | AC | 269 ms
13,760 KB |
testcase_25 | AC | 324 ms
15,328 KB |
ソースコード
// (◕ᴗ◕✿) #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; }