| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 964740 |
2024-04-17T12:44:54 Z |
zxcigan |
Addk (eJOI21_addk) |
C++17 |
|
200 ms |
13692 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1e6 + 1;
const int mod = 1e9 + 7;
template <typename T>
bool umx(T& a, T b) {
return (a < b ? a = b, 1 : 0);
}
template <typename T>
bool umn(T& a, T b) {
return (a > b ? a = b, 1 : 0);
}
ll t[4 * N];
void build (int v, int tl, int tr, vector<ll>&pref) {
if (tl == tr) {
t[v] = pref[tl];
return;
}
int tm = (tr + tl) >> 1;
build (v << 1, tl, tm, pref);
build (v << 1 | 1, tm + 1, tr, pref);
t[v] = t[v << 1] + t[v << 1 | 1];
}
ll lazy[4 * N];
void push (int v, int tl, int tr) {
int tm = (tr + tl) >> 1;
lazy[v << 1] += lazy[v], lazy[v << 1 | 1] += lazy[v];
t[v << 1] += (tm - tl + 1) * lazy[v];
t[v << 1 | 1] += (tr - tm) * lazy[v];
lazy[v] = 0;
}
ll get (int v, int tl, int tr, int l, int r) {
if (l < 1 || r < 1) return 0;
if (l > r) return 0;
if (l == tl && tr == r) return t[v];
if (lazy[v]) push (v, tl, tr);
int tm = (tr + tl) >> 1;
return get (v << 1, tl, tm, l, min (r, tm)) + get (v << 1 | 1, tm + 1, tr, max (l, tm + 1), r);
}
void update (int v, int tl, int tr, int l, int r, ll x) {
if (l > r) return;
if (tl == l && tr == r) {
t[v] += (tr - tl + 1) * x;
lazy[v] += x;
return;
}
if (lazy[v]) push (v, tl, tr);
int tm = (tr + tl) >> 1;
update (v << 1, tl, tm, l, min (r, tm), x);
update (v << 1 | 1, tm + 1, tr, max (l, tm + 1), r, x);
t[v] = t[v << 1] + t[v << 1 | 1];
}
int n, k;
void upd (int pos, int was, int nw) {
update (1, 1, n, pos, n, nw - was);
}
void solve () {
cin >> n >> k;
vector<int> a(n + 1);
vector<ll> pref (n + 1);
vector<ll> ppref (n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i], pref[i] = pref[i - 1] + a[i];
build (1, 1, n, pref);
int q;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 2) {
int l, r, x;
cin >> l >> r >> x;
ll ans = 0;
if (l == 1) {
ans -= get (1, 1, n, 1, r - x);
}
else {
ans -= get (1, 1, n, l - 1, r - x);
}
ans += get (1, 1, n, l + x - 1, r);
cout << ans << "\n";
}
else {
vector<int> ve(k);
for (int i = 0; i < k; ++i) cin >> ve[i];
if (k != 1) {
int last = a[ve[0]];
for (int i = 0; i < k - 1; ++i) {
upd (ve[i], a[ve[i]], a[ve[i + 1]]);
a[ve[i]] = a[ve[i + 1]];
}
upd (ve.back(), a[ve.back()], last);
a[ve.back()] = last;
}
}
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen ("input.txt", "r", stdin);
// freopen ("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
while (T--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2652 KB |
Output is correct |
| 9 |
Correct |
8 ms |
2828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3040 KB |
Output is correct |
| 2 |
Correct |
26 ms |
3420 KB |
Output is correct |
| 3 |
Correct |
35 ms |
3668 KB |
Output is correct |
| 4 |
Correct |
67 ms |
6900 KB |
Output is correct |
| 5 |
Correct |
92 ms |
8020 KB |
Output is correct |
| 6 |
Correct |
87 ms |
7760 KB |
Output is correct |
| 7 |
Correct |
91 ms |
7760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
4900 KB |
Output is correct |
| 2 |
Correct |
114 ms |
11668 KB |
Output is correct |
| 3 |
Correct |
200 ms |
13692 KB |
Output is correct |
| 4 |
Correct |
138 ms |
12708 KB |
Output is correct |
