結果
| 問題 |
No.2065 Sum of Min
|
| コンテスト | |
| ユーザー |
 shotoyoo
|
| 提出日時 | 2022-09-02 22:12:03 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,599 bytes |
| コンパイル時間 | 2,829 ms |
| コンパイル使用メモリ | 223,764 KB |
| 最終ジャッジ日時 | 2025-02-07 01:21:57 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 2 WA * 1 RE * 2 MLE * 15 |
ソースコード
bool TEST = false;
using namespace std;
#include<bits/stdc++.h>
#include<fstream>
#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
#define rrep(i,n) for(ll (i)=(ll)(n)-1;(i)>=0;i--)
#define range(i,start,end,step) for(ll (i)=start;(i)<(ll)(end);(i)+=(step))
#define rrange(i,start,end,step) for(ll (i)=start;(i)>(ll)(end);(i)+=(step))
#define dump(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << (x) << "\n";
#define spa << " " <<
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T>>;
template<typename T, typename T2> using P = pair<T, T2>;
template<typename T, typename T2> using M = map<T, T2>;
template<typename T> using S = set<T>;
template<typename T, typename T2> using UM = unordered_map<T, T2>;
template<typename T> using PQ = priority_queue<T, V<T>, greater<T>>;
template<typename T> using rPQ = priority_queue<T, V<T>, less<T>>;
template<class T>vector<T> make_vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vec(size_t a, Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}
template<class SS, class T> ostream& operator << (ostream& os, const pair<SS, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template <class T> void UNIQUE(vector<T> &x) {sort(all(x));x.erase(unique(all(x)), x.end());}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v){for(ll i=0;i<v.size();i++)
{cerr<<v[i][0];for(ll j=1;j<v[i].size();j++)cerr spa v[i][j];cerr<<"\n";}};
template<typename T> void debug(vector<T>&v){if(v.size()!=0)cerr<<v[0];
for(ll i=1;i<v.size();i++)cerr spa v[i];
cerr<<"\n";};
template<typename T> void debug(priority_queue<T>&v){V<T> vals; while(!v.empty()) {cerr << v.top() << " "; vals.push_back(v.top()); v.pop();} cerr<<"\n"; for(auto val: vals) v.push(val);}
template<typename T, typename T2> void debug(map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n"; cerr<<"\n";}
template<typename T, typename T2> void debug(unordered_map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n";cerr<<"\n";}
V<int> listrange(int n) {V<int> res(n); rep(i,n) res[i]=i; return res;}
template<typename T> P<T,T> divmod(T a, T b) {return make_pair(a/b, a%b);}
const ll INF = (1ll<<62);
// const ld EPS = 1e-10;
// const ld PI = acos(-1.0);
template<typename T>
tuple<V<T>, V<int>, UM<T,int>> press(V<T> &l) {
// xs: index-> original value
// inds: xs[inds[i]] == l[i]
// d: original value -> index
UM<T,int> d;
V<T> xs(l.size());
rep(i,l.size()){
xs[i] = l[i];
}
V<int> inds(l.size());
UNIQUE(xs);
rep(i, xs.size()) d[xs[i]] = i;
rep(i, l.size()) inds[i] = d[l[i]];
return forward_as_tuple(xs, inds, d);
}
template <class T> struct fenwick_tree {
public:
T total;
fenwick_tree() : _n(0) {}
explicit fenwick_tree(int n) : _n(n), data(n), total(0) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
total += x;
while (p <= _n) {
data[p - 1] += T(x);
p += p & -p;
}
}
T query(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return query(r) - query(l);
}
T query(int r) {
T s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
int index(T v) {
// minimum i s.t. a_0 + ... + a_i >= v
// if not exists, return _n
if (v<=0) return 0;
if (total<v) return _n;
int x = 0;
int r = 1;
while (r < _n) r <<= 1;
int l = r;
while (l>0) {
if (x+l < _n and data[x+l-1]<v) {
v -= data[x+l-1];
x += l;
}
l >>= 1;
}
return x;
}
void check () {
rep(i,_n) cout << query(i,i+1) << " ";
cout << endl;
}
private:
int _n;
std::vector<T> data;
};
using BIT = fenwick_tree<ll>;
BIT bit;
void Main(){
ll n,q;
cin >> n >> q;
V<ll> a(n);
V<tuple<ll,ll,ll>> lrx;
rep(i,n) {
cin >> a[i];
}
rep(i,q) {
ll l,r,x;
cin >> l >> r >> x;
l--;
lrx.emplace_back(l,r,x);
a.emplace_back(x);
}
auto [xs,inds,d] = press(a);
rep(i,q) a.pop_back();
int m = xs.size();
int B = 300;
int s = (n+B-1)/B;
rep(i,2*B) a.emplace_back(0);
VV<ll> bs(s);
VV<ll> vs(s);
rep(i,s) {
V<ll> b(m+1);
V<ll> v(m+1);
range(j,B*i,B*(i+1),1) {
b[d[a[j]]+1]++;;
v[d[a[j]]+1] += a[j];
}
rep(i,m) {
b[i+1] += b[i];
v[i+1] += v[i];
}
bs[i] = b;
vs[i] = v;
}
rep(i,q) {
auto [l,r,x] = lrx[i];
int bl = l/B;
int br = r/B;
ll ans = 0;
if (bl==br) {
range(j,l,r,1) {
ans += min(x, a[j]);
}
} else {
range(j,l,(bl+1)*B,1) ans += min(x, a[j]);
range(j,br*B, r, 1) ans += min(x, a[j]);
range(j,bl+1,br,1) {
ll num = bs[j][x];
ll val = vs[j][x];
ans += val + (n-num) * x;
}
}
cout << ans << "\n";
}
}
int main(void){
std::ifstream in("tmp_in");
if (TEST) {
std::cin.rdbuf(in.rdbuf());
std::cout << std::fixed << std::setprecision(15);
} else {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
}
Main();
}