結果

問題 No.1608 Yet Another Ants Problem
ユーザー hitonanode
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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
#endif
    int 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';
}
0