#1168333 (C++17) No.3565 Take from Excluded

• 問題: No.3565 Take from Excluded
• ユーザー: 👑 potato167
• 提出日時: 2026-06-05 22:15:30
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 217 ms / 2,000 ms
• コード長: 3,913 bytes
• コンパイル時間: 1,605 ms
• コンパイル使用メモリ: 230,144 KB
• 実行使用メモリ: 14,628 KB
• 最終ジャッジ日時: 2026-06-05 22:15:53
• 合計ジャッジ時間: 6,271 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 14 TLE * 1 -- * 3

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

#include <atcoder/modint>
using mint = atcoder::modint998244353;

void solve();
// DEAR MYSTERIES / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    rep(i, 0 ,N) cin >> A[i];
    So(A);
    A.erase(unique(all(A)), A.end());
    vector<pair<ll, ll>> p;
    N = A.size();
    for (int l = 0, r = 0; l < N; l = r) {
        while (r != N && A[l] - l == A[r] - r) {
            r++;
        }
        p.push_back({A[l], A[r - 1] + 1});
    }
    auto f = [&](vector<pair<ll, ll>> v, ll m) -> vector<pair<ll, ll>> {
        ll sum = 0;
        vector<pair<ll, ll>> res;
        rep(i, 1, v.size()) {
            if (sum == m) break;
            ll l = v[i - 1].second;
            ll r = v[i].first;
            chmin(r, l + m - sum);
            sum += r - l;
            res.push_back({l, r});
        }
        if (sum != m) res.push_back({v.back().second, v.back().second + m - sum});
        return res;
    };
    mint base = 0;
    while (Q--) {
        ll K, X, M;
        cin >> K >> X >> M;
        auto ans = p;
        if (K < 3) {
            while (K) {
                K--;
                ans = f(ans, M);
            }
        }
        else {
            ans = f(ans, M);
            ans = f(ans, M);
            K -= 2;
            auto ans2 = f(ans, M);
            assert(ans.size() == ans2.size());
            int sz = ans2.size();
            base += (K / (sz * 2)) * M * 2;
            K %= (sz * 2);
            if (K % 2 == 1) {
                swap(ans, ans2);
            }
            rep(rp, 0, K / 2) {
                ans.push_back({ans[rp].first + M * 2, ans[rp].second + M * 2});
            }
            ans.erase(ans.begin(), ans.begin() + (K / 2));
        }
        X--;
        for (auto [l, r] : ans) {
            if (X >= r - l) {
                X -= r - l;
            }
            else {
                cout << (base + X + l).val() << "\n";
                break;
            }
        }
        p = ans;
    }
}

/*
 * 今ある数字の小さい方から N 個
 * 今ない数字の小さい方から N 個を管理するとか？
 * Mi が固定なのがポイントか
 *
 */