結果

問題 No.2065 Sum of Min
コンテスト
ユーザー HIcoder
提出日時 2023-07-13 14:25:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,765 ms / 2,000 ms
コード長 3,512 bytes
コンパイル時間 1,580 ms
コンパイル使用メモリ 120,068 KB
最終ジャッジ日時 2025-02-15 10:13:10
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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];
    }

    /*
    vector<ll> B=A;
    vector<ll> sumA(N,0);
    sumA[0]=A[0];
    for(int i=1;i<N;i++){
        sumA[i]=sumA[i-1]+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());
    }

  

    //auto sumdivT=divT;//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];
        }
        
    }   

    /*
    cout<<"r"<<endl;
    for(int i=0;i<divT.size();i++){
        int sz=divT[i].size();
        
        for(int j=0;j<sz;j++){
            cout<<"i="<<i<<",j="<<j<<",="<<sumdivT[i][j]<<endl;//=sumdivT[i][j-1]+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;
        //cout<<"L[q]="<<L[q]<<",R[q]="<<R[q]<<endl;
        //cout<<"lb="<<lb<<",ub="<<ub<<endl;

        if(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]);
        }

        //cout<<"rangesum="<<rangesum<<endl;


        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-1]の和
            /*
            if(idx-1>=0){
                rangesum+=sumdivT[i][idx-1];
            }
            */
            //[0,idx)の和
            rangesum += sumdivT[i][idx];
           
            //cout<<"num="<<num<<",idx="<<idx<<endl;
            rangesum+=1LL*num*X[q];


        }

        //cout<<"rangesum="<<rangesum<<endl;

        }


        ans[q]=rangesum;

        //cout<<rangesum<<endl;
    }

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

}
0