結果
問題 | No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) |
ユーザー |
![]() |
提出日時 | 2020-08-12 08:18:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 652 ms / 2,000 ms |
コード長 | 1,783 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 127,104 KB |
最終ジャッジ日時 | 2025-01-12 21:10:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, const char**)’: main.cpp:27:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | ll n, q;scanf("%lld %lld", &n,&q); | ~~~~~^~~~~~~~~~~~~~~~~~~~ main.cpp:28:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 28 | vll a(n);re(i, n) scanf("%lld", &a[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:56:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 56 | ll l, r, p;scanf("%lld %lld %lld", &l,&r,&p); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <string> #include <vector> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <bitset> #include <cmath> #include <functional> #include <iomanip> #define vll vector<ll> #define vvvl vector<vvl> #define vvl vector<vector<ll>> #define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c)) #define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c<b;c++) #define all(obj) (obj).begin(), (obj).end() typedef long long int ll; typedef long double ld; using namespace std; #define P 998244353; int main(int argc, char const *argv[]) { ll n, q;scanf("%lld %lld", &n,&q); vll a(n);re(i, n) scanf("%lld", &a[i]); sort(all(a)); reverse(all(a)); vvl dp = VV(n+1, n+1, 0, ll);//i de j ball dp[0][0] = 1; for(int i=0;i<n;i++){ for(int j=0;j<=n;j++){ //使わない場合 dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*(a[i]-1)))%P; //使う場合 dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%P; } } for(int i=0;i<=n;i++){ ll mul = 1; for(int j=i+1;j<=n;j++) mul = (mul * a[j-1])%P; for(int j=0;j<=n;j++) dp[i][j] = (dp[i][j] * mul)%P; } reverse(all(a)); map<ll, ll> mp; for(int i=0;i<n;i++){ auto itr = mp.find(a[i]); if(itr==mp.end()) mp.emplace(a[i], 1); else (*itr).second++; } for(int i=0;i<q;i++){ ll l, r, p;scanf("%lld %lld %lld", &l,&r,&p); ll lb = lower_bound(all(a), l) - a.begin();//l未満いくつ auto itr = mp.lower_bound(l); ll ret = 0; for(int j=l;j<=r;j++){ ll up = n - lb; ret ^= dp[up][p]; if(itr!=mp.end()&&(*itr).first==j) { lb += (*itr).second; itr++; } } printf("%lld\n", ret); } // O(N^2 + Nlog(N) + Q(logN + 200)) return 0; }