結果
問題 | No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) |
ユーザー |
![]() |
提出日時 | 2020-05-29 23:18:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 607 ms / 2,000 ms |
コード長 | 1,732 bytes |
コンパイル時間 | 1,694 ms |
コンパイル使用メモリ | 171,752 KB |
実行使用メモリ | 276,836 KB |
最終ジャッジ日時 | 2024-11-06 07:59:18 |
合計ジャッジ時間 | 5,997 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for(int i = 0; (i) < (n); (i)++)using namespace std;int main(){int N, Q; cin >> N >> Q;long A[7000];REP(i, N) cin >> A[i];int l[7000], r[7000], p[7000];REP(i, Q) cin >> l[i] >> r[i] >> p[i];long mod = 998244353;sort(A, A+N);long dp1[7000], dp2[7000];long ans[7000];REP(i, N) ans[i] = 0l;long mulA[7000];mulA[N] = 1l;REP(i, N) mulA[N-1-i] = (mulA[N-i] * A[i]) % mod;//REP(i, N+1) cout << mulA[i] << " ";//cout << endl;REP(i, N+1) dp1[i] = 0l;dp1[0] = A[N-1]-1l;dp1[1] = 1l;REP(i, Q){for(int j=l[i]; j<=r[i]; j++){int za = (int)(lower_bound(A, A+N, j) - A);if(za == (N-1)){//cout << i << " " << j << " " << dp1[p[i]] * mulA[1] << endl;ans[i] ^= (dp1[p[i]] * mulA[1]) % mod; ans[i] %= mod;}}}long za[7000][7000];REP(k, Q){REP(i, N+1) za[k][i] = 0l;for(int j=l[k]; j<=r[k]; j++){int z = (int)(lower_bound(A, A+N, j) - A);za[k][z]++;}}for(int i = N-2; i>=0; i--){REP(j, N+1) dp2[j] = 0l;REP(j, N+1){dp2[j] += (dp1[j] * (A[i] - 1l)) % mod;dp2[j] %= mod;}REP(j, N){dp2[j+1] += dp1[j];dp2[j+1] %= mod;}REP(j, N+1) dp1[j] = dp2[j];REP(k, Q){long temp = (dp1[p[k]] * mulA[N-i]) % mod;if(za[k][i]%2!=0){ans[k] ^= (dp1[p[k]] * mulA[N-i]) % mod; ans[k] %= mod;}}}REP(i, Q) cout << ans[i] << endl;return 0;}