結果

問題 No.2065 Sum of Min
ユーザー akua
提出日時 2022-09-04 17:34:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,604 bytes
コンパイル時間 3,639 ms
コンパイル使用メモリ 184,376 KB
最終ジャッジ日時 2025-02-07 02:44:14
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;  
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
typedef long long ll;
typedef unsigned long long ull;
const ll inf=1e18;  
using graph = vector<vector<int> > ;
using P= pair<ll,ll>;  
using vi=vector<int>;
using vvi=vector<vi>;
using vll=vector<ll>; 
using vvll=vector<vll>;
using vp=vector<P>;
using vpp=vector<vp>;
//string T="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//string S="abcdefghijklmnopqrstuvwxyz";
//g++ main.cpp -std=c++14 -I .  
//cout <<setprecision(20);
//cout << fixed << setprecision(10);
//cin.tie(0); ios::sync_with_stdio(false);
const double PI = acos(-1);



int main(){cin.tie(0); ios::sync_with_stdio(false);
  int n,q; cin >> n >> q;
  vector<ll>  a(n);rep(i,n)cin >> a[i];
  int x=sqrt(n)+1;
  int si=n/x+2;
  vvi g(si);
  vvll sum(si,vll(x+1));
  rep(i,n)g[i/x].push_back(a[i]);
  rep(i,si)sort(g[i].begin(),g[i].end());
  rep(i,si)rep(j,g[i].size())sum[i][j+1]=sum[i][j]+g[i][j];
  vll anss;
  auto f2=[&](int i,ll k){
     int index=upper_bound(g[i].begin(),g[i].end(),k)-g[i].begin();
     ll res=sum[i][index]+k*(g[i].size()-index);
     return res;
  };
  auto f=[&](int l,int r,ll k){
    ll res=0;
    if(l/x==r/x || r/x-l/x==1){
       repi(i,l,r+1)res+=min(k,a[i]);
    }
    else {
      int now=l;
      while(now/x==l/x){
         res+=min(k,a[now]);
         now++;
      }
      now=(r/x)*x;
      while(now<=r){
        res+=min(k,a[now]);
        now++;
      }
      now=l/x+1;
      while(now<r/x){
        res+=f2(now,k);
        now++;
      }
    }
    return res;
  };
  rep(qi,q){
    int l,r,k; cin >> l >> r >> k;
    l--;r--;
    ll ans=f(l,r,k);
    anss.push_back(ans);
  }
 
  for(auto u:anss)cout << u << endl;

}
0