This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
int n;
vector<long long> a, b;
SegmentTree(int n) : n(n), a(4 * n, 0), b(4 * n, 0) {}
void apply(int idx, long long x, long long y) {
b[idx] = max(b[idx] + x, y);
a[idx] = a[idx] + x;
}
void down(int idx) {
apply(2 * idx + 1, a[idx], b[idx]);
apply(2 * idx + 2, a[idx], b[idx]);
a[idx] = b[idx] = 0;
}
void add(int ql, int qr, long long x, long long y) {
auto dfs = [&](auto self, int idx, int l, int r) {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return apply(idx, x, y);
down(idx);
int m = (l + r) >> 1;
self(self, 2 * idx + 1, l, m);
self(self, 2 * idx + 2, m, r);
};
dfs(dfs, 0, 0, n);
}
long long get(int pos) {
int idx = 0, l = 0, r = n;
while (l + 1 < r) {
down(idx);
int m = (l + r) >> 1;
if (pos < m) {
idx = 2 * idx + 1;
r = m;
} else {
idx = 2 * idx + 2;
l = m;
}
}
return max(a[idx], b[idx]);
}
};
struct Fenwick {
int n;
vector<long long> bit;
Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int i, long long delta) {
for (i++; i <= n; i += i & -i) {
bit[i] += delta;
}
}
void add(int ql, int qr, long long delta) {
add(ql, +delta);
add(qr, -delta);
}
long long get(int i) {
long long res = 0;
for (i++; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> type(q), l(q), r(q), c(q), k(q), a(q), b(q);
for (int i = 0; i < q; i++) {
cin >> type[i];
if (type[i] == 1) {
cin >> l[i] >> r[i] >> c[i] >> k[i];
l[i]--;
}
if (type[i] == 2) {
cin >> l[i] >> r[i] >> k[i];
l[i]--;
}
if (type[i] == 3) {
cin >> a[i] >> b[i];
a[i]--;
b[i]--;
}
}
SegmentTree seg(n);
Fenwick fen(n);
vector<vector<int>> inbox(q + 1);
for (int i = 0; i < q; i++) {
if (type[i] == 1) {
seg.add(l[i], r[i], k[i], 0);
fen.add(l[i], r[i], k[i]);
}
if (type[i] == 2) {
seg.add(l[i], r[i], -k[i], 0);
}
if (type[i] == 3) {
long long seg_get = seg.get(a[i]);
long long fen_get = fen.get(a[i]);
b[i] = fen_get - seg_get + b[i];
l[i] = 0, r[i] = q - 1;
inbox[(l[i] + r[i]) >> 1].push_back(i);
}
}
const int LOG = 18;
for (int ite = 0; ite < LOG; ite++) {
Fenwick fen(n);
vector<vector<int>> new_inbox(q + 1);
for (int m = 0; m < q; m++) {
if (type[m] == 1) {
fen.add(l[m], r[m], k[m]);
}
for (int i : inbox[m]) {
if (b[i] < fen.get(a[i])) {
r[i] = m;
} else {
l[i] = m + 1;
}
new_inbox[(l[i] + r[i]) >> 1].push_back(i);
}
}
inbox = new_inbox;
}
for (int i = 0; i < q; i++) {
if (type[i] == 3) {
if (l[i] > i) {
cout << 0 << '\n';
} else {
cout << c[l[i]] << '\n';
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |