結果
問題 | No.1099 Range Square Sum |
ユーザー | snrnsidy |
提出日時 | 2021-05-11 05:52:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,863 bytes |
コンパイル時間 | 2,156 ms |
コンパイル使用メモリ | 205,984 KB |
実行使用メモリ | 28,216 KB |
最終ジャッジ日時 | 2024-09-21 11:35:18 |
合計ジャッジ時間 | 8,618 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,756 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 54 ms
6,940 KB |
testcase_12 | AC | 54 ms
6,940 KB |
testcase_13 | AC | 54 ms
6,944 KB |
testcase_14 | AC | 57 ms
6,940 KB |
testcase_15 | AC | 52 ms
6,944 KB |
testcase_16 | AC | 54 ms
6,940 KB |
testcase_17 | AC | 56 ms
6,944 KB |
testcase_18 | AC | 57 ms
6,944 KB |
testcase_19 | AC | 59 ms
6,944 KB |
testcase_20 | AC | 56 ms
6,944 KB |
testcase_21 | TLE | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; vector <long long int> v; long long int init(int node, int start, int end, vector<long long>& tree) { if (start == end) { return tree[node] = v[start]; } else { int mid = (start + end) / 2; return tree[node] = init(node * 2, start, mid, tree) + init(node * 2 + 1, mid + 1, end, tree); } } long long int init2(int node, int start, int end, vector<long long>& tree) { if (start == end) { return tree[node] = v[start]*v[start]; } else { int mid = (start + end) / 2; return tree[node] = init2(node * 2, start, mid, tree) + init2(node * 2 + 1, mid + 1, end, tree); } } void lazy(int node, int start, int end, vector<long long>& tree, vector<long long>& l) { if (l[node] != 0) { tree[node] += (end - start + 1) * l[node]; if (start != end) { l[node * 2] += l[node]; l[node * 2 + 1] += l[node]; } l[node] = 0; } } void update(int node, int start, int end, int left, int right, long long int diff, vector<long long>& tree, vector<long long>& l) { lazy(node, start, end, tree, l); if (left > end || right < start) { return; } if (left <= start && end <= right) { tree[node] += (end - start + 1) * diff; if (start != end) { l[node * 2] += diff; l[node * 2 + 1] += diff; } return; } int mid = (start + end) / 2; update(node * 2, start, mid, left, right, diff, tree, l); update(node * 2 + 1, mid + 1, end, left, right, diff, tree, l); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } long long int sum(int node, int start, int end, int left, int right, vector<long long>& tree, vector<long long>& l) { lazy(node, start, end,tree,l); if (left > end || right < start) { return 0; } if (left <= start && end <= right) { return tree[node]; } int mid = (start + end) / 2; return sum(node * 2, start, mid, left, right,tree,l) + sum(node * 2 + 1, mid + 1, end, left, right,tree,l); } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, q; int h, size; cin >> n; h = (int)ceil(log2(n + 100)); size = (1 << (h + 1)) - 1; vector <long long int> tree,tree2; vector <long long int> l,l2; v.resize(n); tree.resize(size); l.resize(size); tree2.resize(size); l2.resize(size); for (int i = 0; i < n; i++) { cin >> v[i]; } init(1, 0, n - 1,tree); init2(1, 0, n - 1, tree2); cin >> q; for (int i = 0; i < q; i++) { int mode, a, b; long long int d; cin >> mode; if (mode == 1) { cin >> a >> b >> d; a -= 1; b -= 1; long long int len = b - a + 1; for (int j = a; j <= b; j++) { long long int add = 2 * d * sum(1, 0, n - 1, j, j, tree, l); add += (d * d); update(1, 0, n - 1, j, j, add, tree2, l2); } update(1, 0, n - 1, a, b, d,tree,l); } else { cin >> a >> b; a -= 1; b -= 1; cout << sum(1, 0, n - 1, a, b,tree2,l2) << '\n'; } } return 0; }