結果
問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
ユーザー | 沙耶花 |
提出日時 | 2021-06-11 22:53:24 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 379 ms / 4,000 ms |
コード長 | 1,307 bytes |
コンパイル時間 | 4,716 ms |
コンパイル使用メモリ | 281,408 KB |
実行使用メモリ | 10,656 KB |
最終ジャッジ日時 | 2023-08-21 13:41:28 |
合計ジャッジ時間 | 11,897 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
4,380 KB |
testcase_01 | AC | 52 ms
4,380 KB |
testcase_02 | AC | 208 ms
4,380 KB |
testcase_03 | AC | 308 ms
6,884 KB |
testcase_04 | AC | 309 ms
7,028 KB |
testcase_05 | AC | 308 ms
6,940 KB |
testcase_06 | AC | 308 ms
6,844 KB |
testcase_07 | AC | 376 ms
10,492 KB |
testcase_08 | AC | 376 ms
10,284 KB |
testcase_09 | AC | 377 ms
10,452 KB |
testcase_10 | AC | 378 ms
10,360 KB |
testcase_11 | AC | 379 ms
10,456 KB |
testcase_12 | AC | 377 ms
10,304 KB |
testcase_13 | AC | 376 ms
10,504 KB |
testcase_14 | AC | 377 ms
10,484 KB |
testcase_15 | AC | 379 ms
10,372 KB |
testcase_16 | AC | 377 ms
10,656 KB |
testcase_17 | AC | 378 ms
10,308 KB |
testcase_18 | AC | 376 ms
10,420 KB |
testcase_19 | AC | 84 ms
4,376 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000000000000000 vector<mint> op(vector<mint> a,vector<mint> b){ a = convolution(a,b); while(a.size() > 3005)a.pop_back(); return a; } vector<mint> e(){ vector<mint> ret(3005,0); ret[0] = 1; return ret; } int main(){ long long N,Q; cin>>N>>Q; vector<long long> K(Q),A(Q),B(Q),S(Q),T(Q); map<long long,int> mp; rep(i,Q){ scanf("%lld %lld %lld %lld %lld",&K[i],&A[i],&B[i],&S[i],&T[i]); K[i]--; if(mp.count(K[i]))continue; int sz = mp.size(); mp[K[i]] = sz; } vector<vector<mint>> temp(mp.size()+1,e()); rep(i,mp.size())temp[i] = vector<mint>(3005,1); long long n = N - mp.size(); vector<mint> Inv(3006,0); rep(i,3006){ if(i!=0)Inv[i] = mint(i).inv(); } rep(i,3005){ mint cur = 1; rep(j,i){ cur *= Inv[j+1]; cur *= i+n-1 - j; } temp.back()[i] = cur; } segtree<vector<mint>,op,e> seg(temp); rep(i,Q){ K[i] = mp[K[i]]; vector<mint> t = seg.get(K[i]); for(int j=A[i];j<=B[i];j++)t[j] = 0; seg.set(K[i],t); t = seg.all_prod(); mint ans = 0; for(int j=S[i];j<=T[i];j++)ans += t[j]; cout<<ans.val()<<endl; } return 0; }