結果

問題 No.2942 Sigma Music Game Level Problem
ユーザー VvyLwVvyLw
提出日時 2024-10-18 23:38:30
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,961 bytes
コンパイル時間 1,569 ms
コンパイル使用メモリ 122,008 KB
実行使用メモリ 19,800 KB
最終ジャッジ日時 2024-10-18 23:38:39
合計ジャッジ時間 9,617 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
19,660 KB
testcase_01 AC 8 ms
19,700 KB
testcase_02 AC 8 ms
19,708 KB
testcase_03 AC 8 ms
19,620 KB
testcase_04 AC 8 ms
19,548 KB
testcase_05 AC 8 ms
19,624 KB
testcase_06 AC 8 ms
19,660 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 454 ms
19,692 KB
testcase_22 AC 542 ms
19,580 KB
testcase_23 WA -
testcase_24 AC 8 ms
19,660 KB
testcase_25 AC 8 ms
19,480 KB
testcase_26 AC 469 ms
19,492 KB
権限があれば一括ダウンロードができます

ソースコード

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 << 20), bit(1 << 20);
    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