結果
問題 | No.2462 七人カノン |
ユーザー |
![]() |
提出日時 | 2023-09-08 21:46:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 450 ms / 2,000 ms |
コード長 | 1,342 bytes |
コンパイル時間 | 3,518 ms |
コンパイル使用メモリ | 256,708 KB |
最終ジャッジ日時 | 2025-02-16 19:45:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll mod=1000000007; ll inf=10090000000000000; int main(){ ll n,q; cin >> n >> q; vector<ll>x(q),s(q),t(q); priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq; for (ll i = 0; i < q; i++) { cin >> x[i] >> s[i]>> t[i]; x[i]--; pq.push({s[i],1}); pq.push({t[i],-1}); } ld y=0; vector<ld>memo(100001,-1); while (!pq.empty()) { pair<ll,ll>p=pq.top(); pq.pop(); y+=p.second; if (y==0) { memo[p.first]=0; continue; } memo[p.first]=1.0/y; } for (ll i = 1; i < memo.size(); i++) { if (memo[i]==-1) { memo[i]=memo[i-1]; } } vector<ld>wa(memo.size(),0); wa[0]=memo[0]; for (ll i = 1; i < wa.size(); i++) { wa[i]=wa[i-1]+memo[i]; } vector<ld>ans(n,0); for (ll i = 0; i < q; i++) { if (s[i]==0) { ans[x[i]]+=wa[t[i]-1]; }else{ ans[x[i]]+=wa[t[i]-1]-wa[s[i]-1]; } } for (ll i = 0; i < n; i++) { cout << setprecision(100) << ans[i] << endl; } }