結果

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

ソースコード

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

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cmath>
#include <numeric>
#include <functional>
#include <cassert>
#include <atcoder/segtree>
#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
template<typename T>
vector<vector<T>> vec2d(int n, int m, T v){
return vector<vector<T>>(n, vector<T>(m, v));
}
template<typename T>
vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));
}
template<typename T>
void print_vector(vector<T> v, char delimiter=' '){
if(v.empty()) {
cout << endl;
return;
}
for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;
cout << v.back() << endl;
}
struct S{
int cnt;
ll sum;
S(int cnt, ll sum): cnt(cnt), sum(sum) {}
};
S op(S x, S y){
return S(x.cnt+y.cnt, x.sum+y.sum);
}
S e(){
return S(0, 0);
}
using Seg = atcoder::segtree<S, op, e>;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(10) << fixed;
int n, q; cin >> n >> q;
vector<ll> a(n);
map<int, vector<int>> adds;
for(int i = 0; i < n; i++) {
cin >> a[i];
adds[a[i]].push_back(i);
}
vector<int> l(q), r(q), x(q);
map<int, vector<int>> queries;
for(int i = 0; i < q; i++) {
cin >> l[i] >> r[i] >> x[i]; l[i]--;
queries[x[i]].push_back(i);
}
auto v = a;
for(int y: x) v.push_back(y);
sort(v.begin(), v.end());
v.erase(unique(begin(v), end(v)), end(v));
Seg seg(n);
vector<ll> ans(q);
for(int x: v){
if(adds.count(x)){
for(int i: adds[x]){
seg.set(i, S(1, x));
}
}
if(queries.count(x)){
for(int i: queries[x]){
auto s = seg.prod(l[i], r[i]);
ans[i] = s.sum + (ll)(r[i]-l[i] - s.cnt)*x;
}
}
}
print_vector(ans, '\n');
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0