| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 829557 |
2023-08-18T12:50:55 Z |
vuavisao |
Addk (eJOI21_addk) |
C++17 |
|
155 ms |
12620 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;
const ll N = 1e5 + 10;
struct SegTree {
struct Node {
ll val[2] = {0, 0};
Node() {};
Node operator + (const Node& other) const {
Node res;
res.val[0] = this -> val[0] + other.val[0];
res.val[1] = this -> val[1] + other.val[1];
return res;
}
};
ll n_node = 0;
vector<Node> tree = {};
void resize(ll _n) { n_node = _n; tree.resize((n_node << 2) + 10); };
SegTree() {};
SegTree(ll _n) { this -> resize(_n); };
void update(ll node, ll l, ll r, ll idx, ll val) {
if(l == r) {
tree[node].val[0] = val;
tree[node].val[1] = val * idx;
return;
}
ll mid = (l + r) >> 1;
if(idx <= mid) update(node << 1, l, mid, idx, val);
else update(node << 1 | 1, mid + 1, r, idx, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
void Update(ll idx, ll val) {
return update(1, 1, n_node, idx, val);
}
Node query(ll node, ll l, ll r, ll L, ll R) {
if(l > r || L > R || l > R || L > r) return Node();
if(L <= l && r <= R) return tree[node];
ll mid = (l + r) >> 1;
return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
}
Node Query(ll l, ll r) {
return query(1, 1, n_node, l, r);
}
};
ll n, q, k;
ll a[N];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
for(ll i = 1; i <= n; ++ i) cin >> a[i];
cin >> q;
SegTree st(n);
for(ll i = 1; i <= n; ++ i) st.Update(i, a[i]);
while(q-- > 0) {
ll type; cin >> type;
if(type == 1) {
ll List[12], val_in_list[12];
for(ll i = 1; i <= k; ++ i) cin >> List[i], val_in_list[i] = a[List[i]];
for(ll i = 1; i <= k; ++ i) {
ll j = i + 1;
if(j > k) j -= k;
a[List[i]] = val_in_list[j];
st.Update(List[i], a[List[i]]);
}
}
else {
ll l, r, m; cin >> l >> r >> m;
// ll le_can_first = l, le_can_last = r - m + 1;
ll use_last = r - m + 1, use_first = l + m - 1;
ll res = 0;
res += st.Query(use_last, use_first).val[0] * (r - m + 1 - l + 1);
const auto& tmp1 = st.Query(max(use_last, use_first + 1), r);
res += (r + 1) * tmp1.val[0] - tmp1.val[1];
const auto& tmp2 = st.Query(l, min(use_last - 1, use_first));
res += tmp2.val[1] - (l - 1) * tmp2.val[0];
res += st.Query(use_first + 1, use_last - 1).val[0] * m;
cout << res << '\n';
}
}
return (0 ^ 0);
}
/// Code by vuavisao
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
4 ms |
604 KB |
Output is correct |
| 5 |
Correct |
5 ms |
724 KB |
Output is correct |
| 6 |
Correct |
7 ms |
852 KB |
Output is correct |
| 7 |
Correct |
6 ms |
856 KB |
Output is correct |
| 8 |
Correct |
7 ms |
980 KB |
Output is correct |
| 9 |
Correct |
10 ms |
1396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2516 KB |
Output is correct |
| 2 |
Correct |
31 ms |
3568 KB |
Output is correct |
| 3 |
Correct |
44 ms |
4652 KB |
Output is correct |
| 4 |
Correct |
79 ms |
7984 KB |
Output is correct |
| 5 |
Correct |
120 ms |
11260 KB |
Output is correct |
| 6 |
Correct |
106 ms |
11092 KB |
Output is correct |
| 7 |
Correct |
107 ms |
11044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
4756 KB |
Output is correct |
| 2 |
Correct |
104 ms |
9388 KB |
Output is correct |
| 3 |
Correct |
155 ms |
12620 KB |
Output is correct |
| 4 |
Correct |
125 ms |
11548 KB |
Output is correct |
