結果
問題 | No.876 Range Compress Query |
ユーザー | Arumakan1727 |
提出日時 | 2019-09-07 16:30:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,945 bytes |
コンパイル時間 | 1,608 ms |
コンパイル使用メモリ | 171,688 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-26 21:33:52 |
合計ジャッジ時間 | 3,073 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | WA | - |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | WA | - |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 55 ms
6,944 KB |
testcase_12 | WA | - |
testcase_13 | AC | 46 ms
6,944 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 54 ms
6,940 KB |
testcase_17 | AC | 53 ms
6,940 KB |
testcase_18 | AC | 59 ms
6,944 KB |
ソースコード
#include "bits/stdc++.h" // Begin Header {{{ #define let const auto #define all(x) (x).begin(), (x).end() #define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i) #define reps(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i) #define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) #define lowerBound(...) lowerBound_(__VA_ARGS__) #define upperBound(...) upperBound_(__VA_ARGS__) #define lowerBound_(begin, end, ...) (lower_bound((begin), (end), __VA_ARGS__) - (begin)) #define upperBound_(begin, end, ...) (upper_bound((begin), (end), __VA_ARGS__) - (begin)) #ifdef DBG #define trace(...) trace_g(#__VA_ARGS__, __VA_ARGS__) #else #define trace(...) #endif using namespace std; using i64 = int_fast64_t; using pii = pair<i64, i64>; template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);} template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);} inline i64 sigma(i64 n) { return (n * (n + 1) >> 1); } inline i64 updiv(i64 a, i64 b) { return (a + b - 1) / b; } inline i64 sqr(i64 n) { return n * n; } inline string to_string(char c) { return string(1, c); } inline bool isRangeIn(i64 a, i64 low, i64 high) { return (low <= a && a <= high); } constexpr int INF = 0x3f3f3f3f; constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL; template<class T> vector<T> makeVec(size_t sz) { return vector<T>(sz); } template<class T, class... Args> auto makeVec(size_t sz, Args... args) { return vector<decltype(makeVec<T>(args...))>(sz, makeVec<T>(args...)); } template<class T> inline void input(T &x) { cin >> x; } template<class Head, class... Tail> inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); } inline void print() { cout << "\n"; } template<class Head, class... Tail> inline void print(Head &&head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << ' '; print(forward<Tail>(tail)...); } template<class T> ostream& operator<< (ostream &out, const vector<T> &vec) { static constexpr const char *delim[] = { " ", "" }; for (const auto &e : vec) out << e << delim[&e == &vec.back()]; return out; } template<class T> ostream& operator<< (ostream &out, const vector<vector<T>> &mat) { static constexpr const char *tail[] = { "\n", "" }; for (const auto &row : mat) out << row << tail[&row == &mat.back()]; return out; } template <class T> void trace_g(const char *s, T&& x) { clog << '{'; while(*s != '\0') clog << *(s++); clog << ":" << setw(3) << x << '}' << endl; } template <class Head, class... Tail> void trace_g(const char *s, Head&& head, Tail&&... tail) { clog << '{'; while(*s != ',') clog << *(s++); clog << ":" << setw(3) << head << "}, "; for (++s; !isgraph(*s); ++s); trace_g(s, std::forward<Tail>(tail)...); } // }}} End Header template <class T> struct FenwickTree { // {{{ vector<T> dat; const int SIZE_POW2; explicit FenwickTree(int size) noexcept : dat(size+5, 0), SIZE_POW2(32 - __builtin_clz(size)) {} inline void add(int i, const T &v) noexcept { for (++i; i < dat.size(); i += i & -i) dat[i]+=v; } inline T operator[](int i) const noexcept { return sum(i, i); } inline void update(int i, const T &newVal) noexcept { const auto curVal = this->operator[](i); add(i, newVal - curVal); assert(this->operator[](i) == newVal); } inline T sum(int i) const noexcept { T s = 0; for (++i; i > 0; i -= i & -i) s += dat[i]; return s; } inline T sum(int s, int t) const noexcept { if (s > t) swap(s, t); return sum(t) - sum(s - 1); } inline int lower_bound(T v) const noexcept { if (v <= 0) return 0; int i = 0; for (int w = SIZE_POW2; w > 0; w >>= 1) { if (i + w < dat.size() && dat[i + w] < v) { v -= dat[i + w]; i += w; } } return i; } }; // }}} signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); var(int, N, Q); vector<i64> a(N); rep(i, N) input(a[i]); vector<i64> d(N - 1); FenwickTree<int> ft(N - 1); rep(i, N - 1) { d[i] = a[i + 1] - a[i]; ft.add(i, (d[i] == 0 ? 0 : 1)); } while (Q--) { var(int, com, l, r); --l, --r; if (com == 1) { var(i64, x); if (l > 0) { d[l - 1] += x; ft.update(l - 1, d[l - 1] == 0 ? 0 : 1); } if (r < N - 1) { d[r] -= x; ft.update(r, d[r] == 0 ? 0 : 1); } } else { print(1 + ft.sum(l, r - 1)); } } return 0; }