結果
問題 | No.1608 Yet Another Ants Problem |
ユーザー |
![]() |
提出日時 | 2021-07-16 23:26:10 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,137 bytes |
コンパイル時間 | 3,938 ms |
コンパイル使用メモリ | 120,564 KB |
最終ジャッジ日時 | 2025-01-23 02:46:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#pragma GCC optimize("Ofast,unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")#include <algorithm>#include <iostream>#include <vector>using namespace std;#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)#define REP(i, n) FOR(i,0,n)template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <int md> struct ModInt {#if __cplusplus >= 201402L#define MDCONST constexpr#else#define MDCONST#endifint val;MDCONST ModInt() : val(0) {}MDCONST ModInt &_setval(int v) { return val = (v >= md ? v - md : v), *this; }MDCONST ModInt(int v) { _setval(v); }MDCONST explicit operator bool() const { return val != 0; }MDCONST ModInt operator+(const ModInt &x) const { return ModInt()._setval(val + x.val); }MDCONST ModInt operator-(const ModInt &x) const { return ModInt()._setval(val - x.val + md); }MDCONST ModInt operator-() const { return ModInt()._setval(md - val); }MDCONST ModInt &operator+=(const ModInt &x) { return *this = *this + x; }MDCONST ModInt &operator-=(const ModInt &x) { return *this = *this - x; }MDCONST friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val; }};using mint = ModInt<998244353>;int main() {cin.tie(nullptr), ios::sync_with_stdio(false);int N, L;cin >> N >> L;vector<int> A(N);for (auto &x : A) cin >> x;vector<vector<int>> w2i(N);REP(i, N) {if (i and A[i - 1] >= L - A[i]) break;int r = lower_bound(A.begin() + i + 1, A.end(), L - A[i]) - A.begin();w2i[N - 1 - (r - i - 1)].push_back(i + (r - i - 1));}REP(i, N) {if (i + 1 < N and L - A[i + 1] > A[i]) continue;int l = lower_bound(A.begin(), A.begin() + i, L - A[i]) - A.begin() - 1;w2i[N - 1 - (i - l - 1)].push_back(l + 1 + (i - l - 1));}vector<mint> ret(N);for (auto is : w2i) {REP(i, ret.size() - 1) ret[i] += ret[i + 1];for (auto i : is) ret[i] += 1;}for (auto x : ret) cout << x << '\n';}