#1192609 (C++23) No.3761 Moonlit Battle

• 問題: No.3761 Moonlit Battle
• ユーザー: ZeriToki
• 提出日時: 2026-10-09 23:49:37
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,841 bytes
• コンパイル時間: 2,295 ms
• コンパイル使用メモリ: 349,796 KB
• 実行使用メモリ: 27,148 KB
• 最終ジャッジ日時: 2026-10-09 23:49:54
• 合計ジャッジ時間: 6,826 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 27 WA * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
const long long mod100=1000000007;

template<typename T> struct segtree{
    //0-indexed
    using F = function<T(T,T)>;
    int n, offset;
    vector<T>node;
    F op;
    T identity;
    segtree(int N, F op, T identity):op(op), identity(identity){
        offset = 1;
        n = N;
        while(offset < N) offset <<= 1;
        node.assign(offset*2, identity);
    }

    T operator[](int p){
        return node[p+offset];
    }

    //seg[p]をxに変更する
    void set(int p, T x){
        if(p < 0 || p >= offset){
            if(p < 0) cerr << "segtree in set:p < 0"<<endl;
            if(p >= offset) cerr << "segtree in set:p >= offset"<<endl;
            return;
        }
        p += offset;
        node[p] = x;
        while(p >= 2){
            p >>= 1;
            node[p] = op(node[p*2], node[p*2+1]);
        }
        return;
    }

    //[l,r)の区間を取得する
    T fold(int l,int r){
        if(l < 0){
            cerr << "segtree in fold:l < 0" << endl;
            l = 0;
        }
        if(l >= offset){
            cerr << "segtree in fold:l >= offset" << endl;
            l = offset - 1;
        }
        if(r < 0){
            cerr << "segtree in fold:r < 0" << endl;
            r = 0;
        }
        if(r > offset){
            cerr << "segtree in fold:r >= offset" << endl;
            r = offset;
        }
        l += offset;
        r += offset;
        T L=identity,R=identity;
        for(; l < r; l >>= 1, r >>= 1){
            if(l & 1) L = op(L, node[l++]);
            if(r & 1) R = op(node[--r], R);
        }
        return op(L,R);
    }

    //f(l,r)=trueとなるrの最大値を取得
    int max_right(const function<bool(T)>f, int l = 0){
        if(l >= n) return n;
        if(l < 0){
            cerr << "segtree in max_right: l < 0" << endl;
            l = 0;
        }
        l += offset;
        T sum = identity;
        do{
            while(l % 2 == 0) l >>= 1;
            if(!f(op(sum, node[l]))){
                while(l < offset){
                    l = l * 2;
                    if(f(op(sum, node[l]))){
                        sum = op(sum,node[l]);
                        ++l;
                    }
                }
                return l - offset;
            }
            sum = op(sum, node[l]);
            ++l;
        } while ((l & -l) != l);
        return n;
    }

    //f(l,r)=trueとなる最小のlを取得
    int min_left(const function<bool(T)>f, int r = -1){
        if(r == 0) return 0;
        if(r < 0) r = n;
        r += offset;
        T sum = identity;
        do{
            --r;
            while(r > 1 && (r & 1)) r >>= 1;
            if(!f(op(node[r], sum))){
                while(r < offset){
                    r = r * 2 + 1;
                    if(f(op(node[r], sum))){
                        sum = op(node[r], sum);
                        --r;
                    }
                }
                return r + 1 - offset;
            }
            sum = op(node[r], sum);
        } while((r & -r) != r);
        return 0;
    }
};

int main(){
    cout.tie()->sync_with_stdio(0);
    cin.tie(0);
    
    int N;ll D;cin>>N>>D;
    pair<ll,ll>AB[N+1];
    ll A[N+1],B[N+1],C[N+1];
    vector<ll>press;
    for(int i=1;i<=N;i++){
        cin>>AB[i].second>>AB[i].first;
        press.push_back(AB[i].first%D);
    }
    sort(AB+1,AB+N+1);
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=1;i<=N;i++){
        A[i]=AB[i].second;
        B[i]=AB[i].first;
        auto it=lower_bound(press.begin(),press.end(),B[i]%D);
        int idx=distance(press.begin(),it);
        C[i]=idx+1;
        //cout<<idx<<endl;
    }


    auto op=[](ll a,ll b){return a+b;};
    segtree<ll>seg(N+1,op,0LL);

    for(int i=1;i<=N;i++){
        seg.set(C[i],seg[C[i]]+A[i]);
    }

    ll plus=0;
    for(int i=1;i<=N;i++) plus+=(B[i]+D-1)/D*A[i];
    ll ans=plus;

    for(int i=1;i<=N;i++){
        seg.set(C[i],seg[C[i]]-A[i]);
        plus-=(B[i]+D-1)/D*A[i];

        ll now=B[i]+plus;
        //cout<<plus<<" ";

        now-=seg.fold(1,N+1)*(B[i]/D);
        //cout<<now<<" ";
        ll x=B[i]%D;
        auto it=upper_bound(press.begin(),press.end(),x);
        int idx=distance(press.begin(),it);
        now-=seg.fold(1,idx+1);
        //cout<<idx<<" "<<now<<endl;
        //for(int j=1;j<=N;j++) cout<<seg[j]<<" ";
        //cout<<endl;
        chmin(ans,now);


    }
    cout<<ans<<endl;

}