結果
| 問題 | No.833 かっこいい電車 |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-05-25 03:38:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 145 ms / 2,000 ms |
| コード長 | 6,819 bytes |
| コンパイル時間 | 1,924 ms |
| コンパイル使用メモリ | 205,640 KB |
| 最終ジャッジ日時 | 2025-01-07 04:03:59 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#pragma GCC diagnostic ignored "-Wsign-compare"#pragma GCC diagnostic ignored "-Wsign-conversion"#define NDEBUG#define SHOW(...) static_cast<void>(0)//!===========================================================!////! dP dP dP !////! 88 88 88 !////! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !////! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !////! 88 88 88. ... 88. .88 88. .88 88. ... 88 !////! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !////!===========================================================!//template <typename T, typename A>std::istream& operator>>(std::istream& is, std::vector<T, A>& v){for (auto& e : v) { is >> e; }return is;}template <typename T>T read(){T v;return std::cin >> v, v;}template <typename T>std::vector<T> readVec(const std::size_t l){std::vector<T> v(l);for (auto& e : v) { std::cin >> e; }return v;}using ld = long double;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr unsigned int MOD = 1000000007;template <typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template <typename F>constexpr F PI = static_cast<F>(3.1415926535897932385);std::mt19937 mt{std::random_device{}()};template <typename T>bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }template <typename T>bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }template <typename T>std::vector<T> Vec(const std::size_t n, T v) { return std::vector<T>(n, v); }template <class... Args>auto Vec(const std::size_t n, Args... args) { return std::vector<decltype(Vec(args...))>(n, Vec(args...)); }template <typename T>constexpr T popCount(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : (T)__builtin_popcountll(u);#elseunsigned long long v = static_cast<unsigned long long>(u);return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v= (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);#endif}template <typename T>constexpr T log2p1(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : T(64 - __builtin_clzll(u));#elseunsigned long long v = static_cast<unsigned long long>(u);return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32),popCount(v);#endif}template <typename T>constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }template <typename T>constexpr T msbp1(const T v) { return log2p1(v); }template <typename T>constexpr T lsbp1(const T v){#ifdef __has_builtinreturn __builtin_ffsll(v);#elsereturn v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);#endif}template <typename T>constexpr bool ispow2(const T v) { return popCount(v) == 1; }template <typename T>constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }template <typename T>constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }//!================================================================!////! 88888888b oo dP !////! 88 88 !////! a88aaaa .d8888b. 88d888b. dP dP dP dP .d8888b. 88 .dP !////! 88 88ooood8 88' '88 88 88 88 88 88' '"" 88888" !////! 88 88. ... 88 88 88.88b.88' 88 88. ... 88 '8b. !////! dP '88888P' dP dP 8888P Y8P dP '88888P' dP 'YP !////!================================================================!//template <typename T = ll>class Fenwick{public:Fenwick(const std::size_t N, const T initial = T{}) : size(N), cap(ceil2(size)), value(cap + 1, 0){if (initial != T{}) {std::fill(value.begin() + 1, value.end(), initial);for (std::size_t x = 1; x < cap; x++) { value[x + (x & -x)] += value[x]; }}}template <typename InIt>Fenwick(const InIt first, const InIt last) : size(std::distance(first, last)), cap(ceil2(size)), value(cap + 1, 0){std::copy(first, last, value.begin() + 1);for (std::size_t x = 1; x < cap; x++) { value[x + (x & -x)] += value[x]; }}void add(const std::size_t a, const T& val){assert(a < size);for (std::size_t ind = a + 1; ind <= cap; ind += ind & (-ind)) { value[ind] += val; }}T sum(const std::size_t a) const{assert(a <= size);T sum{};for (std::size_t ind = a; ind != 0; ind &= ind - 1) { sum += value[ind]; }return sum;}T sum(const std::size_t l, const std::size_t r) const { return assert(l < r), assert(r <= size), sum(r) - sum(l); }std::size_t partitionPoint(const T val) const{if (val < 0) { return 0; }std::size_t x = 0;T offset = 0;for (std::size_t k = ((cap == size) ? cap : cap / 2); k != 0; k >>= 1) {if (x + k <= cap and value[x + k] + offset <= val) { offset += value[x + k], x += k; }}return std::min(x, size);}friend std::ostream& operator<<(std::ostream& os, const Fenwick& fw){os << "[";for (std::size_t i = 0; i < fw.size; i++) { os << fw.sum(i, i + 1) << (i + 1 == fw.size ? "" : ","); }return (os << "]\n");}private:const std::size_t size, cap;std::vector<T> value;};//!============================================!////! 8888ba.88ba oo !////! 88 '8b '8b !////! 88 88 88 .d8888b. dP 88d888b. !////! 88 88 88 88' '88 88 88' '88 !////! 88 88 88 88. .88 88 88 88 !////! dP dP dP '88888P8 dP dP dP !////!============================================!//int main(){const int N = read<int>(), Q = read<int>();const auto A = readVec<ll>(N);Fenwick<ll> bit(A.begin(), A.end());std::set<int> right;for (int i = 0; i <= N; i++) { right.insert(i); }for (int q = 0; q < Q; q++) {SHOW(right, bit);int t, x;std::cin >> t >> x;if (t == 1) {right.erase(x);} else if (t == 2) {right.insert(x);} else if (t == 3) {bit.add(x - 1, 1);} else {auto it = right.lower_bound(x);const int r = *it;const int l = *std::prev(it);std::cout << bit.sum(l, r) << std::endl;}}return 0;}