結果

問題 No.2942 Sigma Music Game Level Problem
コンテスト
ユーザー VvyLw
提出日時 2024-10-18 23:37:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,961 bytes
コンパイル時間 2,123 ms
コンパイル使用メモリ 120,512 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-11-07 22:06:12
合計ジャッジ時間 8,996 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#ifdef local
#include <C++/core/io/debug_print.hpp>
#else
#define dump(...) void(0);
#endif

#include <iostream>
#include <ranges>
#include <vector>
#include <algorithm>
namespace man {
template <class T> struct FenwickTree {
private:
    int n;
    std::vector<T> data;
    void init(const size_t size) {
        n = size + 2;
        data.resize(n + 1);
    }
public:
    FenwickTree(){}
    FenwickTree(const size_t size){ init(size); }
    FenwickTree(const std::vector<T> &a) {
        init(a.size());
        for(size_t i = 0; i < a.size(); ++i) {
            add(i, a[i]);
        }
    }
    T sum(int k) const {
        if(k < 0) {
            return 0;
        }
        T ret = 0;
        for(++k; k > 0; k -= k & -k) {
            ret += data[k];
        }
        return ret;
    }
    inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }
    inline T operator[](int k) const { return sum(k) - sum(k - 1); }
    void add(int k, const T &x) {
        for(++k; k < n; k += k & -k) {
            data[k] += x;
        }
    }
    void add(const int l, const int r, const T& x) {
        add(l, x);
        add(r + 1, -x);
    }
    int lower_bound(T w) {
        if(w <= 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
    int upper_bound(T w) {
        if(w < 0) {
            return 0;
        }
        int x = 0;
        for(int k = 1 << std::__lg(n); k; k >>= 1) {
            if(x + k <= n - 1 && data[x + k] <= w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x;
    }
};

/**
 * @brief Binary Indexed Tree
 * @see https://nyaannyaan.github.io/library/data-structure/binary-indexed-tree.hpp
 */
}
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    using namespace std::views;
    int n, q, l0;
    std::cin >> n >> q >> l0;
    man::FenwickTree<int64_t> cnt(1 << 18), bit(1 << 18);
    for([[maybe_unused]] const auto _: iota(0, n)) {
        int a;
        std::cin >> a;
        cnt.add(a, 1);
        bit.add(a, a);
    }
    bool none = true;
    for([[maybe_unused]] const auto _: iota(0, q)) {
        int t;
        std::cin >> t;
        if(t == 1) {
            int l;
            std::cin >> l;
            cnt.add(l, 1);
            bit.add(l, l);
        } else if(t == 2) {
            none = false;
            int l, r;
            std::cin >> l >> r;
            r++;
            std::cout << cnt.sum(l, r) << ' ' << bit.sum(l, r) << '\n';
        } else {
            int m;
            std::cin >> m;
        }
    }
    if(none) {
        std::cout << "Not Found!\n";
    }
}
0