結果

問題 No.2065 Sum of Min
ユーザー HIcoder
提出日時 2023-07-13 14:27:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,778 ms / 2,000 ms
コード長 2,792 bytes
コンパイル時間 1,407 ms
コンパイル使用メモリ 118,872 KB
最終ジャッジ日時 2025-02-15 10:13:33
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
バケットソート
*/
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<cmath>
#include <unordered_set>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=998244353;


int main(){
    int N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }



    const int T=max(1,(int)sqrt(N));//適当

    vector<vector<ll>> divT;

    {
        /*
        0番目が 0~T-1,
        1番目が T~2*T-1,
        2番目が 2*T ~ 3*T-1
        3番目が 3*T ~ 4*T-1

        */
        vector<ll> tmp;
        for(int i=0;i<N;i++){
            if(i>0 && i%T==0){
                divT.push_back(tmp);
                tmp.clear();
                tmp.push_back(A[i]);
            }else{
                tmp.push_back(A[i]);
            }
        }

        if(tmp.size()>0){
            divT.push_back(tmp);
        }

    }

   


    for(auto &vec:divT){
        //バケット内ではソートしておく
        sort(vec.begin(),vec.end());
    }

  

    //divT[i]はソートされた状態

    vector<vector<ll>> sumdivT(divT.size());

    for(int i=0;i<divT.size();i++){
        int sz=divT[i].size();

        sumdivT[i].resize(sz+1);

        sumdivT[i][0]=0;
        for(int j=0;j<sz;j++){
            sumdivT[i][j+1]=sumdivT[i][j]+divT[i][j];
        }
        
    }   


   

    vector<int> L(Q),R(Q);
    vector<ll> X(Q);


    vector<ll> ans(Q);

    for(int q=0;q<Q;q++){
    
        cin>>L[q]>>R[q]>>X[q];
        L[q]--;R[q]--;

        ll rangesum=0;

       

        int lb=(L[q]+(T-1))/T;
        int ub=R[q]/T;

        if(lb>=ub){
            //T=5でL[q]=1, R[q]=2とかのとき. lb>ubとなるので

            for(int i=L[q];i<=R[q];i++){
                rangesum+=min(A[i],X[q]);
            }


        }else{


        for(int l=L[q];l<lb*T;l++){
            
            rangesum+=min(A[l],X[q]);
        }

        for(int r=ub*T;r<=R[q];r++){
            rangesum+=min(A[r],X[q]);
        }


        for(int i=lb;i<ub;i++){
            //区間に完全に入っている

            auto it=upper_bound(divT[i].begin(),divT[i].end(),X[q]);

            //divT[i]のなかでX[i]より大きい数
            int num=divT[i].end()-it;//X[i]
            
            //divT[i]のなかでX[q]を超える最初のインデックス
            int idx=it-divT[i].begin();
           
        
            //[0,idx)の和
            rangesum += sumdivT[i][idx];
           

            rangesum+=1LL*num*X[q];


        }

      

        }


        ans[q]=rangesum;

      
    }

    for(ll v:ans){
        cout<<v<<endl;
    }

}
0