#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define int long long
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 250010
using namespace std;
template<typename T>
T &ckmin(T &a, T b) {
return a = min(a, b);
}
struct BIT {
int n;
vector<ll> bit;
BIT(int n) : n(n), bit(n) {}
void upd(int x, ll q) {
x++;
while (x <= n) {
bit[x - 1] += q;
x += x & -x;
}
}
ll qry(int x) {
ll res = 0;
while (x > 0) {
res += bit[x - 1];
x -= x & -x;
}
return res;
}
int bsearch(ll r) {
int cur = 0;
ll sum = 0;
for (int i = (1 << 20); i > 0; i /= 2) {
if (cur + i <= n && sum + bit[cur + i - 1] <= r) {
cur += i;
sum += bit[cur - 1];
}
}
return cur;
}
};
BIT tot_add(0);
struct segtree {
int n;
vector<ll> st;
vector<ll> lazy;
segtree(int n) : n(n), st(4 * n), lazy(4 * n) {}
void push(int v, int l, int r) {
if (l + 1 != r) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
ckmin(lazy[2 * v], st[2 * v]);
ckmin(lazy[2 * v + 1], st[2 * v + 1]);
}
st[v] -= lazy[v];
lazy[v] = 0;
}
void upd(int x, int y, ll q) { upd(1, 0, n, x, y, q); }
void upd(int v, int l, int r, int x, int y, ll q) {
push(v, l, r);
ckmin(q, st[v]);
if (r <= x || l >= y) return;
if (x <= l && r <= y) {
lazy[v] += q;
push(v, l, r);
} else {
int m = (l + r) / 2;
upd(2 * v, l, m, x, y, q);
upd(2 * v + 1, m, r, x, y, q);
st[v] = max(st[2 * v], st[2 * v + 1]);
}
}
ll qry(int a, ll b) { return qry(1, 0, n, a, b); }
ll qry(int v, int l, int r, int a, ll b) {
push(v, l, r);
if (l + 1 == r) {
if (b >= st[v]) {
return -1;
} else {
return tot_add.qry(a + 1) - st[v] + b;
}
} else {
int m = (l + r) / 2;
if (a < m) {
return qry(2 * v, l, m, a, b);
} else {
return qry(2 * v + 1, m, r, a, b);
}
}
}
};
int n, m, q;
array<ll, 5> qry[MAXN];
vector<pair<ll, int>> in_q;
vector<int> add[MAXN]; // elements to add to the queue
vector<int> rem[MAXN]; // elements to remove from the queue
vector<pair<ll, int>> to_ans[MAXN];
vector<ll> ans;
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 0; i < q; i++) {
qry[i] = {0, 0, 0, 0, 0};
cin >> qry[i][0];
switch (qry[i][0]) {
case 1:
cin >> qry[i][1] >> qry[i][2] >> qry[i][3] >> qry[i][4];
break;
case 2:
cin >> qry[i][1] >> qry[i][2] >> qry[i][3];
break;
case 3:
cin >> qry[i][1] >> qry[i][2];
break;
}
}
segtree st(n);
tot_add = BIT(n);
for (int i = 0; i < q; i++) {
auto qq = qry[i];
if (qq[0] == 1) {
auto [t, l, r, c, k] = qq;
l--;
add[l].push_back(in_q.size());
rem[r].push_back(in_q.size());
in_q.push_back({k, c});
st.upd(l, r, -k);
tot_add.upd(l, k);
tot_add.upd(r, -k);
} else if (qq[0] == 2) {
auto [t, l, r, k, _] = qq;
l--;
st.upd(l, r, k);
} else {
auto [t, a, b, _, __] = qq;
a--; b--;
int p_idx = st.qry(a, b);
to_ans[a].push_back({p_idx, ans.size()});
ans.emplace_back();
}
}
int sz = in_q.size();
BIT bit(sz);
for (int i = 0; i < n; i++) {
for (int x : add[i]) {
bit.upd(x, in_q[x].first);
}
for (int x : rem[i]) {
bit.upd(x, -in_q[x].first);
}
for (auto [loc, idx] : to_ans[i]) {
if (loc == -1) {
ans[idx] = 0;
} else {
int pos = bit.bsearch(loc);
ans[idx] = in_q[pos].second;
}
}
}
for (int x : ans) {
cout << x << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
18124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
18124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
28720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
485 ms |
53176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
18124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
29264 KB |
Output is correct |
| 2 |
Correct |
111 ms |
29420 KB |
Output is correct |
| 3 |
Correct |
108 ms |
30304 KB |
Output is correct |
| 4 |
Correct |
85 ms |
27704 KB |
Output is correct |
| 5 |
Correct |
106 ms |
29048 KB |
Output is correct |
| 6 |
Correct |
118 ms |
30280 KB |
Output is correct |
| 7 |
Correct |
42 ms |
23336 KB |
Output is correct |
| 8 |
Correct |
39 ms |
23068 KB |
Output is correct |
| 9 |
Correct |
61 ms |
29112 KB |
Output is correct |
| 10 |
Correct |
79 ms |
26776 KB |
Output is correct |
| 11 |
Correct |
101 ms |
29376 KB |
Output is correct |
| 12 |
Correct |
103 ms |
29544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
18124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
18124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
