#794811 (C++17(clang)) No.2065 Sum of Min

提出ソース

結果

問題	No.2065 Sum of Min
ユーザー	shotoyoo
提出日時	2022-09-02 22:07:09
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	RE
実行時間	-
コード長	6,507 bytes
コンパイル時間	3,228 ms
コンパイル使用メモリ	171,776 KB
実行使用メモリ	545,828 KB
最終ジャッジ日時	2024-04-27 21:41:37
合計ジャッジ時間	15,601 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	MLE	-
testcase_10	TLE	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp:3:17: warning: using directive refers to implicitly-defined namespace 'std'
    3 | using namespace std;
      |                 ^
1 warning generated.

ソースコード

raw source code

 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,B - (n%B)) a.emplace_back(0);
    V<BIT> bs(s);
    V<BIT> vs(s);
    rep(i,s) {
        BIT b(m);
        BIT v(m);
        range(j,B*i,B*(i+1),1) {
            b.add(d[a[j]], 1);
            v.add(d[a[j]], a[j]);
        }
        bs[i] = b;
    }
    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].query(x);
                ll val = vs[j].query(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();
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード