結果

問題 No.2065 Sum of Min
ユーザー HIcoderHIcoder
提出日時 2023-07-13 14:27:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,776 ms / 2,000 ms
コード長 2,792 bytes
コンパイル時間 1,374 ms
コンパイル使用メモリ 121,736 KB
実行使用メモリ 7,924 KB
最終ジャッジ日時 2023-10-13 03:24:57
合計ジャッジ時間 19,293 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 478 ms
7,752 KB
testcase_05 AC 759 ms
7,856 KB
testcase_06 AC 937 ms
7,736 KB
testcase_07 AC 694 ms
7,916 KB
testcase_08 AC 583 ms
7,856 KB
testcase_09 AC 266 ms
7,760 KB
testcase_10 AC 1,776 ms
7,800 KB
testcase_11 AC 1,766 ms
7,852 KB
testcase_12 AC 836 ms
7,916 KB
testcase_13 AC 835 ms
7,916 KB
testcase_14 AC 835 ms
7,740 KB
testcase_15 AC 835 ms
7,792 KB
testcase_16 AC 837 ms
7,744 KB
testcase_17 AC 841 ms
7,920 KB
testcase_18 AC 837 ms
7,908 KB
testcase_19 AC 829 ms
7,860 KB
testcase_20 AC 834 ms
7,924 KB
testcase_21 AC 834 ms
7,848 KB
権限があれば一括ダウンロードができます

ソースコード

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