結果
問題 | No.876 Range Compress Query |
ユーザー | define |
提出日時 | 2019-09-07 12:43:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,461 bytes |
コンパイル時間 | 1,863 ms |
コンパイル使用メモリ | 175,144 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-06-26 08:31:28 |
合計ジャッジ時間 | 12,729 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | WA | - |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 1,297 ms
9,344 KB |
testcase_12 | AC | 1,061 ms
9,344 KB |
testcase_13 | AC | 1,100 ms
9,344 KB |
testcase_14 | AC | 1,265 ms
9,344 KB |
testcase_15 | AC | 985 ms
9,344 KB |
testcase_16 | AC | 1,318 ms
9,472 KB |
testcase_17 | AC | 1,333 ms
9,344 KB |
testcase_18 | AC | 1,397 ms
9,472 KB |
ソースコード
#include <bits/stdc++.h>#define int long long#define mod (int)(1e9+7)#define inf (int)(3e18)#define rep(i,n) for(int i=0;i<n;i++)#define REP(i,n) for(int i=1;i<n;i++)#define P pair<int,int>#define PiP pair<int,pair<int,int>>#define PP pair<P,P>#define all(v) v.begin(),v.end()#define mkp make_pair#define mkt make_tuple#define prique(T) priority_queue<T,vector<T>,greater<T>>#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())using namespace std;template<class T> inline void chmax(T& a, T b) { a = max(a, b); }template<class T> inline void chmin(T& a, T b) { a = min(a, b); }bool prime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0)return false;}return x != 1;}int gcd(int x, int y) {if (y == 0)return x;return gcd(y, x % y);}int lcm(int x, int y) {return x / gcd(x, y) * y;}int kai(int x, int y) {int res = 1;for (int i = x - y + 1; i <= x; i++) {res *= i; res %= mod;}return res;}int mod_pow(int x, int y, int m) {int res = 1;while (y > 0) {if (y & 1) {res = res * x % m;}x = x * x % m;y >>= 1;}return res;}int comb(int x, int y) {if (y > x)return 0;return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;}int get_rand(int MIN, int MAX) {random_device rnd;mt19937_64 mt64(rnd());uniform_int_distribution<int>engine(MIN, MAX);return engine(mt64);}/*--------Library Zone!--------*/struct Segtree {int size = 1;vector<int>dat, lazy, ans;Segtree(int x) {while (size < x)size *= 2;lazy.resize(2 * size - 1);dat.resize(2 * size - 1);ans.resize(2 * size - 1);rep(i, 2 * size - 1) {dat[i] = 0; lazy[i] = 0; ans[i] = 0;}}void eval(int k, int l, int r) {dat[k] += lazy[k];if (r - l > 1) {lazy[k * 2 + 1] += lazy[k] / 2;lazy[k * 2 + 2] += lazy[k] / 2;}lazy[k] = 0;}int query(int a, int k = 0, int l = 0, int r = -1) {if (r == -1)r = size;eval(k, l, r);if (r - l == 1)return dat[k];if (a < (l + r) / 2) {return query(a, k * 2 + 1, l, (l + r) / 2);}return query(a, k * 2 + 2, (l + r) / 2, r);}void update(int a, int b, int x, int k = 0, int l = 0, int r = -1) {if (r == -1)r = size;eval(k, l, r);if (r <= a || b <= l)return;if (a <= l && r <= b) {lazy[k] += x * (r - l);eval(k, l, r);if(r-l==1)ans[k]=1;return;}update(a, b, x, k * 2 + 1, l, (l + r) / 2);update(a, b, x, k * 2 + 2, (l + r) / 2, r);int lval = query((l + r) / 2 - 1), rval = query((l + r) / 2);if (lval == rval) {ans[k] = max(0ll,ans[k * 2 + 1] + ans[k * 2 + 2] - 1);}else {ans[k] = ans[k * 2 + 1] + ans[k * 2 + 2];}}int query2(int a, int b, int k = 0, int l = 0, int r = -1) {if (r == -1)r = size;eval(k, l, r);if (r <= a || b <= l)return 0;if (a <= l && r <= b) {return ans[k];}int lval = query2(a, b, k * 2 + 1, l, (l + r) / 2);int rval = query2(a, b, k * 2 + 2, (l + r) / 2, r);int lval2 = query((l + r) / 2 - 1);int rval2 = query((l + r) / 2);return lval + rval - (lval2 == rval2&&lval2);}};int n, q;signed main() {cin >> n >> q;Segtree segtree(n);rep(i, n) {int a; cin >> a;segtree.update(i, i + 1, a);}rep(i, q) {int a, b, c, d;cin >> a >> b >> c;b--; c--;if (a == 1) {cin >> d;segtree.update(b, c, d);}else {cout << segtree.query2(b, c + 1) << endl;}}}