結果

問題 No.2065 Sum of Min
ユーザー KKT89
提出日時 2022-09-02 21:56:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 2,350 bytes
コンパイル時間 1,585 ms
コンパイル使用メモリ 144,652 KB
最終ジャッジ日時 2025-02-07 01:12:21
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <sstream>
#include <utility>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <array>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
// 1-indexed
template<typename T>
struct BIT{
int n;
vector<T> bit;
BIT(int n_=0):n(n_),bit(n+1){}
T sum(int i){
T res=0;
for(;i>0;i-=(i&-i))res+=bit[i];
return res;
}
void add(int i,T a){
if(i==0)return;
for(;i<=n;i+=(i&-i)){bit[i]+=a;}
}
int lower_bound(T k){ // k<=sum(res)
if(k<=0)return 0;
int res=0,i=1;
while((i<<1)<=n)i<<=1;
for(;i;i>>=1){
if(res+i<=n&&bit[res+i]<k)k-=bit[res+=i];
}
return res+1;
}
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n,q; cin >> n >> q;
BIT<ll> bit(n),cnt(n);
vector<pair<pair<int,int>,pair<int,int>>> v;
for(int i=0;i<n;i++){
int a; cin >> a;
v.push_back({{a,i+1},{-1,-1}});
}
vector<ll> res(q);
for(int i=0;i<q;i++){
int l,r,x; cin >> l >> r >> x;
v.push_back({{x,i},{l,r}});
}
sort(v.begin(), v.end());
for(auto &p:v){
if(p.second.first == -1){
int idx = p.first.second;
int a = p.first.first;
bit.add(idx, a);
cnt.add(idx, 1);
}
else{
int idx = p.first.second;
ll cn = cnt.sum(p.second.second) - cnt.sum(p.second.first-1);
ll su = bit.sum(p.second.second) - bit.sum(p.second.first-1);
res[idx] = su + (ll)(p.second.second-p.second.first+1-cn)*(ll)p.first.first;
}
}
for(int i=0;i<q;i++){
cout << res[i] << "\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0