/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 250010;
const ll inf = 1e18;
struct node
{
ll min_val, min_lf, min_rf;
node(ll _min_val = inf, ll _min_lf = -1, ll _min_rf = -1)
{
min_val = _min_val;
min_lf = _min_lf;
min_rf = _min_rf;
}
};
node merge_nodes(node lf, node rf)
{
if (lf.min_val < rf.min_val)
return lf;
if (rf.min_val < lf.min_val)
return rf;
node cur = lf;
if (lf.min_rf == rf.min_lf - 1)
{
cur.min_rf = rf.min_rf;
}
return cur;
}
struct segment_tree
{
node tree[4 * maxn];
ll lazy[4 * maxn];
void push_lazy(int root, int left, int right)
{
tree[root].min_val += lazy[root];
if (left != right)
{
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
}
lazy[root] = 0;
}
void build(int root, int left, int right)
{
if (left == right)
{
tree[root].min_lf = left;
tree[root].min_rf = right;
tree[root].min_val = 0;
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int qleft, int qright, ll cur)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = cur;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update(root * 2, left, mid, qleft, qright, cur);
update(root * 2 + 1, mid + 1, right, qleft, qright, cur);
tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}
node query(int root, int left, int right, int qleft, int qright)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return merge_nodes(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
};
int n, m, q;
void input()
{
cin >> n >> m >> q;
}
struct task
{
int idx;
ll pos;
task(int _idx = 0, ll _pos = 0)
{
idx = _idx;
pos = _pos;
}
};
struct bit
{
ll fen[maxn];
void update(int pos, ll val)
{
for (int i = pos; i < maxn; i += (i & -i))
fen[i] += val;
}
ll query(int pos)
{
ll sum = 0;
for (int i = pos; i > 0; i -= (i & -i))
sum += fen[i];
return sum;
}
void range_update(int l, int r, ll v)
{
update(l, v);
update(r + 1, - v);
}
int find_kth(ll to)
{
int pos = 0;
ll sum = 0;
for (int bit = 20; bit >= 0; bit --)
{
if (pos + (1 << bit) > maxn)
continue;
ll new_sum = sum + fen[pos + (1 << bit)];
if (new_sum < to)
{
pos = pos + (1 << bit);
sum = new_sum;
}
}
return pos + 1;
}
};
vector < task > ask[maxn];
segment_tree line_tree;
bit pass_tree;
int ans[maxn];
pair < int, ll > add[maxn];
vector < int > upd[maxn];
int query_cnt = 0;
void simulate()
{
line_tree.build(1, 1, n);
int t, l, r, c, a; /// careful overflow
ll k, b;
int cnt = 0;
for (int i = 1; i <= q; i ++)
{
cin >> t;
if (t == 1)
{
cin >> l >> r >> c >> k;
line_tree.update(1, 1, n, l, r, k);
add[i] = {c, k};
upd[l].push_back(i);
upd[r + 1].push_back(-i);
}
else
if (t == 2)
{
cin >> l >> r >> k;
line_tree.update(1, 1, n, l, r, -k);
pass_tree.range_update(l, r, k);
node cur;
while(true)
{
cur = line_tree.query(1, 1, n, l, r);
if (cur.min_val >= 0)
break;
pass_tree.range_update(cur.min_lf, cur.min_rf, cur.min_val);
line_tree.update(1, 1, n, cur.min_lf, cur.min_rf, - cur.min_val);
cnt ++;
}
}
else
{
cin >> a >> b;
query_cnt ++;
if (line_tree.query(1, 1, n, a, a).min_val < b)
{
ans[query_cnt] = 0;
}
else
{
///cout << "here " << query_cnt << " " << pass_tree.query(a) << " " << line_tree.query(1, 1, n, a, a).min_val << endl;
ask[a].push_back(task(query_cnt, pass_tree.query(a) + b));
}
}
}
assert(cnt <= 2 * n);
}
bit active;
void answer_tasks()
{
for (int i = 1; i <= n; i ++)
{
for (int cur : upd[i])
{
if (cur > 0)
{
active.update(cur, add[cur].second);
}
else
{
active.update(-cur, - add[-cur].second);
}
}
for (task cur : ask[i])
{
ans[cur.idx] = add[active.find_kth(cur.pos)].first;
///cout << cur.idx << " : " << cur.shop << " " << cur.pos << endl;
}
}
for (int i = 1; i <= query_cnt; i ++)
{
cout << ans[i] << endl;
}
}
void solve()
{
input();
simulate();
answer_tasks();
}
int main()
{
speed();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
44120 KB |
Output is correct |
| 4 |
Correct |
9 ms |
43864 KB |
Output is correct |
| 5 |
Runtime error |
38 ms |
88660 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
44120 KB |
Output is correct |
| 4 |
Correct |
9 ms |
43864 KB |
Output is correct |
| 5 |
Runtime error |
38 ms |
88660 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
48992 KB |
Output is correct |
| 2 |
Correct |
139 ms |
49488 KB |
Output is correct |
| 3 |
Correct |
109 ms |
49168 KB |
Output is correct |
| 4 |
Correct |
147 ms |
49292 KB |
Output is correct |
| 5 |
Correct |
119 ms |
49516 KB |
Output is correct |
| 6 |
Correct |
116 ms |
49488 KB |
Output is correct |
| 7 |
Runtime error |
54 ms |
93624 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
494 ms |
55376 KB |
Output is correct |
| 2 |
Correct |
552 ms |
54300 KB |
Output is correct |
| 3 |
Correct |
437 ms |
55760 KB |
Output is correct |
| 4 |
Correct |
304 ms |
55120 KB |
Output is correct |
| 5 |
Correct |
262 ms |
54276 KB |
Output is correct |
| 6 |
Correct |
358 ms |
56344 KB |
Output is correct |
| 7 |
Runtime error |
97 ms |
97216 KB |
Execution killed with signal 6 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
44120 KB |
Output is correct |
| 4 |
Correct |
9 ms |
43864 KB |
Output is correct |
| 5 |
Runtime error |
38 ms |
88660 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
47952 KB |
Output is correct |
| 2 |
Correct |
61 ms |
47956 KB |
Output is correct |
| 3 |
Correct |
62 ms |
48208 KB |
Output is correct |
| 4 |
Correct |
46 ms |
47684 KB |
Output is correct |
| 5 |
Correct |
54 ms |
47952 KB |
Output is correct |
| 6 |
Correct |
71 ms |
48208 KB |
Output is correct |
| 7 |
Correct |
23 ms |
44756 KB |
Output is correct |
| 8 |
Correct |
23 ms |
44856 KB |
Output is correct |
| 9 |
Correct |
48 ms |
47136 KB |
Output is correct |
| 10 |
Correct |
42 ms |
46928 KB |
Output is correct |
| 11 |
Correct |
61 ms |
47172 KB |
Output is correct |
| 12 |
Correct |
59 ms |
47184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
44120 KB |
Output is correct |
| 4 |
Correct |
9 ms |
43864 KB |
Output is correct |
| 5 |
Runtime error |
38 ms |
88660 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
8 ms |
43864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
44120 KB |
Output is correct |
| 4 |
Correct |
9 ms |
43864 KB |
Output is correct |
| 5 |
Runtime error |
38 ms |
88660 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
