#include <bits/stdc++.h>
using namespace std;
int const N = 1 << 18;
struct LazySegTree {
struct Node {
int his = 0;
int cur = 0;
friend Node operator*(Node ret, int val) {
ret.cur += val;
ret.his = min(ret.his, ret.cur);
return ret;
}
friend Node operator+(Node a, Node b) {
Node ret;
ret.cur = a.cur + b.cur;
ret.his = min(a.his, a.cur + b.his);
return ret;
}
};
array<Node, 2 * N> seg;
void propagate(int ver, int lx, int rx) {
if (rx - lx == 1) return;
seg[2 * ver + 1] = seg[2 * ver + 1] + seg[ver];
seg[2 * ver + 2] = seg[2 * ver + 2] + seg[ver];
seg[ver] = {0, 0};
}
void add(int l, int r, int val, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (rx <= l || r <= lx) return;
if (l <= lx && rx <= r) {
seg[ver] = seg[ver] * val;
return;
}
int mx = (lx + rx) / 2;
add(l, r, val, 2 * ver + 1, lx, mx);
add(l, r, val, 2 * ver + 2, mx, rx);
}
int query(int p, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (rx - lx == 1) return seg[ver].his;
int mx = (rx + lx) / 2;
if (p < mx) return query(p, 2 * ver + 1, lx, mx);
else return query(p, 2 * ver + 2, mx, rx);
}
};
LazySegTree st1;
struct SegTree {
struct Node{
int cur = 0;
int lazy = 0;
friend Node operator*(Node ret, int val) {
ret.cur += val;
ret.lazy += val;
return ret;
}
friend Node operator+(Node a, Node b) {
Node ret;
ret.cur = min(a.cur, b.cur);
return ret;
}
};
array<Node, 2 * N> seg;
void propagate(int ver, int lx, int rx) {
if (rx - lx == 1) return;
seg[2 * ver + 1] = seg[2 * ver + 1] * seg[ver].lazy;
seg[2 * ver + 2] = seg[2 * ver + 2] * seg[ver].lazy;
seg[ver].lazy = 0;
}
void pull(int ver) {
seg[ver] = seg[2 * ver + 1] + seg[2 * ver + 2];
}
void upd(int l, int r, int val, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (rx <= l || r <= lx) return;
if (l <= lx && rx <= r) {
seg[ver] = seg[ver] * val;
return;
}
int mx = (lx + rx) / 2;
upd(l, r, val, 2 * ver + 1, lx, mx);
upd(l, r, val, 2 * ver + 2, mx, rx);
pull(ver);
}
int query(int l, int r, int ver, int lx, int rx) {
propagate(ver, lx, rx);
if (rx <= l || r <= lx) return INT_MAX;
if (l <= lx && rx <= r) {
return seg[ver].cur;
}
int mx = (rx + lx) / 2;
int t1 = query(l, r, 2 * ver + 1, lx, mx);
int t2 = query(l, r, 2 * ver + 2, mx, rx);
return min(t1, t2);
}
};
SegTree st;
struct Item {
int t, l, r, c, k, a, b, bio = 1, time = 0;
Item() {
t = l = r = c = k = a = b = -1;
}
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<Item> queries(q);
vector<vector<int>> events(n + 10);
int idx = 0;
int tim = 0;
for (auto &[t, l, r, c, k, a, b, bio, time] : queries) {
cin >> t;
if (t == 1) {
cin >> l >> r >> c >> k;
--l;
events[l].push_back(idx);
events[r].push_back(idx);
st1.add(l, r, k, 0, 0, N);
} else if (t == 2) {
cin >> l >> r >> k;
k = -k;
--l;
events[l].push_back(idx);
events[r].push_back(idx);
st1.add(l, r, k, 0, 0, N);
} else {
cin >> a >> b;
--a;
b += st1.query(a, 0, 0, N);
time = tim++;
events[a].push_back(idx);
}
++idx;
}
vector<int> ans(tim);
set<int> s;
for (auto const &vec : events) {
for (auto i : vec) {
if (queries[i].t != 3) {
st.upd(i, N, queries[i].k * queries[i].bio, 0, 0, N);
if (queries[i].k > 0) {
if (queries[i].bio == 1) s.insert(i);
else s.erase(i);
}
queries[i].bio *= -1;
} else {
if (s.empty() || st.query(i, i + 1, 0, 0, N) < queries[i].b) {
ans[queries[i].time] = 0;
continue;
}
if (st.query(i, i + 1, 0, 0, N) == queries[i].b) {
auto it = s.lower_bound(i);
assert(it != s.begin());
--it;
ans[queries[i].time] = queries[*it].c;
continue;
}
int lo = 0, hi = i;
while (lo < hi) {
int mid = (lo + hi) / 2;
int x = st.query(mid, i, 0, 0, N);
//cerr << x << '\n';
if (x <= queries[i].b) {
lo = mid + 1;
} else hi = mid;
}
auto it = s.lower_bound(lo);
if (it == s.begin()) {
ans[queries[i].time] = queries[*it].c;
} else {
if (st.query(*prev(it), *it, 0, 0, N) == queries[i].b) {
ans[queries[i].time] = queries[*prev(it)].c;
} else {
ans[queries[i].time] = queries[lo].c;
}
}
}
}
}
for (auto a : ans) cout << a << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
9232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
29576 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
8404 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
